CODEWITHSUNDEEP
c++recursionfibonacci
slick
slick

Reputation: 65

How does recursion work when there are two recursive calls in a same statement?

I have recently taken up studying algorithms and data structures.I came across fibonacci problem and its solution using recursion. But thats the thing. I understand how recursive calls work when there is only one(like in factorial of a number).The function calls keep on stacking up until they hit the base case and then they start unraveling by one to the desired answer.

But What I dont get is how does recursion work when there are two recursive calls in an expression like f(n)+f(n/2). I mean which call is resolved first and when does the second call gets resolved. Also how is the sum calculated if this expression is assigned to a statement? I wrote a small code to decipher this myself.

#include <iostream>
#include <string>


int main()
{
  int recursionTest(int n, char c);
  int x;
  std::cin>>x;
  std::cout<<"Ans:"<<recursionTest(x,'c');

}


int recursionTest(int n,char c)
{
   int result=0;
   if(n==0)
    return 1;
   std::cout<<n<<":"<<c<<std::endl;
   result=recursionTest(n/2,'L')+recursionTest(n/3,'R');////I cant figure 
                                                           out the flow of 
                                                           control here!!!
   return result;
}

And I got the following output. 

24
24:c
12:L
6:L
3:L
1:L
1:R
2:R
1:L
4:R
2:L
1:L
1:R
8:R
4:L
2:L
1:L
1:R
2:R
1:L
Ans:20

SO I get it ,its a tree structure. But I still dont know how we are getting 20 as answer(input=24). How is the sum expression working and what is it summing,how can I look at the tree structure and generate the same out put?

Binary Tree representation of output

Upvotes: 1

Views: 2335

Answers (2)

Ananth
Ananth

Reputation: 462

Here operator precedence will play the role 

f(n) + f(n/2);

In the above code snippet f(n) will get called first and then f(n/2). basically arithmetic operators compile from left to right. If you want to debug the code use printf statements inside function f(int) by printing n value . By this you can get the hang of the code

Upvotes: -1

Ken Thomases
Ken Thomases

Reputation: 90551

There is no defined order to how the two subexpressions of the + operator are evaluated. The compiler can emit code to evaluate either one first and the other one second. It can even interleave some computations of one side with computations of the other. For example, it could calculate n/3, then n/2, then the right function call, and finally the left function call.

The flow control is just like for a single case of recursion followed by another single case. So, your line:

result=recursionTest(n/2,'L')+recursionTest(n/3,'R');

is effectively the same as:

int left = recursionTest(n/2,'L');
int right = recursionTest(n/3,'R');
result = left + right;

except for the implication in my version that the left function call is guaranteed to be evaluated before the right function call.

Upvotes: 2

Related Questions