recursion

[vgoel38]

does recursion in fabonacci series take place like this??

formula used : fb(n)=fb(n-1)+fb(n-2)

e.g. to calculate fb(4)

step1: fb(4)=fb(3)+fb(2)
step2: call fb(3)
step3: fb(3)=fb(2)+fb(1)
step4: call fb(2)
step5: fb(2)=fb(1)+fb(0)
step6: call fb(1)
step7: fb(1)=1 is returned..goes back to step 5
step8: call fb(0)
step9: fb(0)=0 is returned..goes back to step 5
step10:fb(2)=1+0=1 is returned..goes back to step3
step11:call fb(1)
step12:fb(1)=1 is returned to step3
step12:fb(3)=1+1=2 is returned to step1
step13: fb(2) is calculated by step4+5+6+7+8+9..returned to step1
step14:fb(4)=2+1=3 returned to main func

is this the critreria recursion follows?? if yes..it means..everything is not done simultaneously...it is done step by step..

[vgoel38]

i think i got it...if i understand it using stacks..it becomes easier..but my new ques is..can every recursion can be understood using stacks..or should i ask..
is recursion based on concept of stack?

[Volatile Pulse]

The thing to remember about C++ is that it's still a linear language (it goes from top to bottom until it reaches the end) (obvious exceptions for threading). When dealing with recursion, just look at it as a statement that doesn't finish for a while. Some recursion can be rather long, while other recursion can be really short.

When I try to code recursion, I attempt to work backward, the last step first. This is easiest for me since the last step typically has a conditional to terminate the recursion. In basic recursion, it's sometimes easy to look at it as if it's a for loop, The assignment is the initial call to the function, the conditional is what would eventually terminate the recursion, and the increment is what each step of the recursion should do. Fibonacci is a hard, first recursion example. I'd suggest starting with a simpler recursion like factorial. The concept is much easier to grasp when starting small.

The issue I have with the fibonacci recursion is that you have to decide which way you want your recursion to process. When you call Fibonacci, do you want to give it the number of terms (total amount of recursion) or do you want to give it a number and count up to see what term number you entered. I have always used fibonacci in a loop of some sort and then set the function up correctly to handle it. I don't recall specifically making a fibonacci recursion function, but the concept isn't hard once you figure out your path.