CODEWITHSUNDEEP
c++recursionrecursive-backtracking
Akram ElectroTech
Akram ElectroTech

Reputation: 173

Comprehending the walk through of a recursive code

If I keep my hand on each line of code as we go through, then when we hit a function call, my hand goes to the function which is called and that function begins to execute, after that my hand returns back to the line where the function was called.

Now when it comes to recursion, when I keep calling the same function, how does the hand behave? Is there a new hand for each function call? I don't understand how the code "goes back up a tree of recursive calls". I understand there is a stack. I have seen all those videos explaining it.

What I don't understand is that if I write cout statements, one above and one under the recursive call, then I understand why the cout statement above the recursive call executes as many times as the recursive function is being called, but then how does the cout statement below the recursive call also get executed those many times? Here's an example

int Factorial(int n)
{
  cout<<"first cout statement before the recursive call";
  if( n == 0 )
     return 1;
  int F = n*Factorial(n-1);
  cout<<"second cout statement after the recursive call";
  return F; 
}
int main()
{
 int n;
 cin>>n;
 int result = Factorial(n);
 cout<<result;
}

This the output below. 

first cout statement before the recursive call
first cout statement before the recursive call
first cout statement before the recursive call
first cout statement before the recursive call
first cout statement before the recursive call
first cout statement before the recursive call

second cout statement after the recursive call  //Notice these
second cout statement after the recursive call
second cout statement after the recursive call
second cout statement after the recursive call
second cout statement after the recursive call
120

Upvotes: 0

Views: 101

Answers (1)

cdhowie
cdhowie

Reputation: 169018

Think of the call stack like a tray of index cards. The stack starts out empty. The only things you can do are write down a new index card and put it on the top, or take whatever is on the top off.

There is some stuff in that tray put there by the runtime, but for the moment let's just pretend that the tray is empty when main() starts to run.

Pretend that each function is a chapter in a book. Each page has a bunch of individual sentences that each tell you to do one specific thing. One of those things could be "go to another chapter and do what it says, using this information I have here." When you reach such a sentence, you need to remember how to get back to where you were, so you write down the following on an index card:

  • What chapter you are currently in and what sentence of the chapter you just read (maybe page number, paragraph number, and sentence number within that paragraph, for example).
  • Any of the information you were working with before you were asked to go to another chapter.

You put this card on the top of the tray, then you turn to the other chapter and start doing stuff.

When you get to a sentence that says "you are done with this chapter, go back to the last chapter with this result" then you take the card off of the top, turn back to whatever chapter it says, find the sentence immediately following the one the card indicates, and you proceed from there.

That's all that's happening here. Chapters are functions. Sentences are machine instructions. Stuff you take to the other chapter are function arguments. Stuff you take back from a chapter is the return value. The "stuff you were working with" that you put down on the index card is the value of any function-local variables at the time a function call was made.

When you make a recursive call, you still put something on the stack, but you just go to the same chapter you were already reading -- just with slightly different information. When you need to leave the chapter, the top card might say that you are still in the same chapter, but on a different sentence and with different information.

You have a series of nested calls, one stack frame per recursive invocation. When control returns out of the recursive call, you're still in the same function -- but with the same local variable values you had before the call.

So in your case, yes, you could think of it that you have "multiple hands." However deep you were recursing into the same function, you have to work your way back up as each recursive call returns.

There honestly is no difference whatsoever between recursive calls and non-recursive calls in the way that the program flow logically progresses (except in the case of tail-call optimization). The compiler and machine code don't care that the same function is called, it performs the same process either way.

Upvotes: 2

Related Questions