I am trying to understand the recursion call in the below code snippet.
static long fib(int n) {
return n <= 1 ? n : fib(n-1) + fib(n-2);
}
Which function call does get called first? How does the equation work after the calls?
Do both of these get called once and then equation applied or first one called and then the 2nd one?
Maybe a very simple question!
Sub-expressions are evaluated in left-to-right order. fib(n-1) is evaluated before fib(n-2). See What are the rules for evaluation order in Java?
It's important to note that the order of evaluation doesn't matter here since fib() does not have any side effects.
The two functions are called in an indeterminate order, and once both have been called their return values are added together and returned. The left function could be called first, or the right one first, you don't know.
That may seem problematic, but it's not, because the order they're called doesn't matter. Calling fib(i) does not have any side effects (e.g. modifying other variables, printing a message, etc.), so the two function calls are entirely independent.
One compiler might 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 one might decide to evaluate the right side before 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
The order of evaluation for the + operator might not be defined (it's implementation-dependent) meaning: either fib(n-1) or fib(n-2) could be executed first. Either way the result will be the same, in this particular case it doesn't matter: both recursive calls will be computed and added together before being returned, from the calling place you'll only see the end result of the sum.
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 that the first two in the sequence are 0 and 1).
So what this function does to work out fib(n) is to ask for fib(n-1) and fib*(n-2) and add them together to get fib(n). Of course, fib(n-1) works by asking for fib(n-2) and fib(n-3), while fib(n-2) works by asking for fib(n-3) and fib(n-4) and so on until the very beginning of the sequence (0 and 1) is reached. Since those can be returned without any further recursion, the recursion ends and each open function returns to the one that called it, all the way back up the chain.
There's a more efficient way to do this which doesn't require two separate recursions, but it wouldn't look so elegant.
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, it call fib also for (n-2) without knowing that the right branch is also calculating the same thing.
This well known example has a complexity of O(n^2), meaning that if n=10, it calls it self with different parameters ~100 times, even though 10 times is more than enough.
To understand this i used below code and the output cleared all the doubt:(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 left expression then move to right.
