Recursion - two calls in one application

Question

I am trying to understand the recursion call in the code snippet below.

static long fib(int n) { return n <= 1 ? n : fib(n-1) + fib(n-2); } 

What function call is called first? How does the equation work after calls?

Are both of them called once, and then the equation is applied, or the first, and then the second?

Maybe a very simple question!

Answer 1

Java and C & sharp;

Subexpressions are evaluated in order from left to right. fib(n-1) evaluates to fib(n-2) . See What are the rules for evaluation order in Java?

It is important to note that the order of evaluation is not important here, since fib() has no side effects.

C and C ++

Two functions are called in an undefined order, and as soon as both are called, their return values ​​are added together and returned. The left function could be called first or right, you do not know.

This may seem problematic, but it is not, because the order they call does not matter. The fib(i) call has no side effects (for example, changing other variables, printing a message, etc.), so the two function calls are completely independent.

One compiler may decide to evaluate the left side before the right:

  1. f(3) 2. f(2) 3. f(1) 4. return 1 5. f(0) 6. return 0 7. return 1 + 0 8. f(1) 9. return 1 10. return 1 + 1 

Another may decide to evaluate the right side in front of the left:

  1. f(3) 2. f(1) 3. return 1 4. f(2) 5. f(0) 6. return 0 7. f(1) 8. return 1 9. return 1 + 0 10. return 1 + 1 

Answer 2

The evaluation order for the + operator cannot be determined (implementation dependent), that is: either fib(n-1) or fib(n-2) can be executed first. In any case, the result will be the same, in this particular case it does not matter: both recursive calls will be calculated and added before returning, from the calling place you will see only the final result of the sum.

Answer 3

It doesn't matter which function is called first. This function returns the nth number in the Fibonacci sequence, which can always be found by adding the previous two numbers together (with the special case when the first two in the sequence are 0 and 1).

So what this function does to produce fib (n) is to ask fib (n-1) and fib * (n-2) and add them together to get fib (n). Of course, fib (n-1) works by querying fib (n-2) and fib (n-3), and fib (n-2) works by accessing fib (n-3) and fib (n-4)) and so on until the very beginning of the sequence (0 and 1) is reached. Since they can be returned without any further recursion, the recursion ends, and each open function returns to the one that called it, completely restoring the chain.

There's a more efficient way to do this that doesn't require two separate recursions, but it doesn't look so elegant.

Answer 4

Gcc -S fib.c:

  subl $1, %eax movl %eax, (%esp) call _fib movl %eax, %ebx movl 8(%ebp), %eax subl $2, %eax movl %eax, (%esp) call _fib 

So, the left one is called first. What then? Well, he also calls fib for (n-2) without knowing that the correct branch also computes the same thing.

This well-known example has complexity O (n ^ 2), which means that if n = 10, he calls it "I" with different parameters ~ 100 times, even if 10 times is more than enough.

Answer 5

To understand this, I used the code below, and the output cleared all doubts: (C #)

  static void Main(string[] args) { var data = series(5); Console.WriteLine(data); } public static int series(int n) { Console.WriteLine(n); if (n ==2) { return 1; } if (n == 50) { return 3; } else { return series(2) + series(50); } } 

Output: 5 2 50 4

In short, it will complete the recursion of the left expression, then move to the right.