Geek Answers Handbook

Give a tough analysis while this code snippet is running

public static long F (int N) { if ( N == 1 ) return 1; return F(N - F(N-1)); }

Now I thought that inside F (N-1) would execute N times for each of F (N - F (N-1)), and so it would be N 2 but that doesn not seem to be the answer.

Can someone tell me why?

+6
source share
1 answer

To understand this, suppose we rewrite this code in an equivalent way:

 public static int F (int N) { if ( N == 1 ) return 1; int k = F(N - 1); return F(N - k); }

All I did was pull out the internal call F(N - 1) and transfer it to the upper level, so that we can more clearly see that this code makes two calls to F and that the second call is to a subtask, which depends on the first call.

To determine the execution time, we need to find out what k is, so that we can see what kind of recursive call we are making. Interestingly, F (N) = 1 for all N. Here you can define this pattern:

  • F (1) = 1.
  • F (2) = F (2 - F (1)) = F (2 - 1) = F (1) = 1
  • F (3) = F (3 - F (2)) = F (3 - 1) = F (2) = 1
  • F (4) = F (4 - F (3)) = F (4 - 1) = F (3) = 1

This is a great exercise to prove it by induction.

So this means that calling F (N - k) will call F (N - 1). This means that the code is functionally equivalent.

 public static int F (int N) { if ( N == 1 ) return 1; int k = F(N - 1); return F(N - 1); }

It has a recursive relationship

  • F (1) = 1
  • F (n) = 2F (n-1) + 1

Which solves F (n) = 2 n - 1. (Again, you can officially prove this by induction if you want). Therefore, complexity is & Theta; (2 n ).

To test this, here is a (really hacked) C script that calls a function on several different inputs, reporting the returned value and the number of calls made:

 #include <stdio.h> /* Slightly modified version of F that tracks the number of calls made * using the second out parameter. */ static int F (int N, int* numCalls) { /* Track the number of calls. */ (*numCalls)++; if ( N == 1 ) return 1; return F (N - F (N-1, numCalls), numCalls); } int main() { for (int i = 1; i < 10; i++) { int numCalls = 0; int result = F(i, &numCalls); printf("F(%d) = %d, making %d calls.\n", i, result, numCalls); } }

Output signal

 F(1) = 1, making 1 calls. F(2) = 1, making 3 calls. F(3) = 1, making 7 calls. F(4) = 1, making 15 calls. F(5) = 1, making 31 calls. F(6) = 1, making 63 calls. F(7) = 1, making 127 calls. F(8) = 1, making 255 calls. F(9) = 1, making 511 calls.

Note that the F (i) score always takes 2 i - 1 calls (as the theory predicted!) And always returns 1, empirically checking the mathematical analysis.

+9
source

More articles:


All Articles