clarification on recursion concept

Question

I am having doubt on recursion, if I write the code like shown below

inorder(p){
if(p!=NULL){
 inorder(p->link);  //step 1
 cout<<p->info<<" "; //step 2
 inorder(p->link);  //step 3
}
} 

Here, my doubt is that when step 1 is executed the control goes back to the function and then again the step 1 executes and again the control will go back to the function up to p is NULL, if this is the process then how control will come to step 2 which is "cout" and to step 3 ...

I am unable to cycle the code in my brain...

Answer 1

Each time the function inorder is called, data (referred to as an activation frame or frame) is put on data structure referred to as a call stack. Each frame keeps track of data local to the function, such as parameters passed into the function, a pointer to the activation frame of the function caller and, importantly, the address of the next line of code to be executed in the calling function. So as you recursively call inorder, you are recursively adding frames to this stack and each frame contains an address to the next line of code that should be executed when the corresponding function is finished and control is returned to the function caller.

In other words, when you call inorder from line referred to as step 1 and the passed in parameter p is NULL, when the function exits, the calling function will start execution at the line referred to as step 2.

See the wikipedia page http://en.wikipedia.org/wiki/Call_stack for more info.

Understanding the concepts related to call stacks will help in understanding what is going on with recursion.

Answer 2

Consider a game, were you have 5 messages left at different places in your house. Each message leads you to the next. To win the game, you must find all 5 messages and return them to the game host. However, you cannot pick up the messages as you find them... you must remember their location and pick them up in the opposite order you found them.

You would walk to the first item, make a note of where it is and follow the clue; keeping a mental note to where you need to return later to pick up the clue. You would do the same with the next 4 clues.

When you find the last clue, so no more exist, you would then start to work backwards, returning to where you found each clue, retrieving them.

Finding the first clue is like your first call to "inorder()". Following the clue to the second clue is like your call to "inorder(p->link)". Picking up the clue after all clues have been found is like when you return to "step2" in your code.

Answer 3

I assume that your code is correct. You are trying to print out a linked list in the below fashion:

inorder(p){ 
 if(p!=NULL)
 {
   inorder(p->link);   //step 1 to navigate to next link
   cout<<p->info<<" "; //step 2 as main operation
   inorder(p->link);   //step 3 to navigate to next link
 }
} 

Translate into English

inorder(p)
{
  if p points to a linked list
  {
    print the list p points to;
    print content of p;
    print the list p points to again;
  }

  if p points to a null linked list     
  {
     do nothing;
  }
}

Then a linked list of 1 -> 2 -> 3 will output ((3) 2 (3)) 1 ((3) 2 (3))

As you can see, the control will only pass to step 2 once step 1 encounters a null linked list. After the info is printed out, it is then passed to step 3.

Therefore,

• When linked list at node "3",

  step 1 encounters null and return;

  step 2 prints out 3;

  step 3 encounters null and return;

• When linked list at node "2"

  step 1 performs whatever it does at node "3"; // print 3

  step 2 prints out 2;

  step 3 performs whatever it does at node "3"; // print 3

• when linked list at node "1"

  step 1 performs whatever it does at node "2"; // print 3 2 3

  step 2 prints out 1;

  step 3 performs whatever it does at node "2"; // print 3 2 3

Answer 4

When the first call to inorder(p->link) is made, consider it as a checkpoint. It will keep calling to a point it reaches NULL. Then line 2 is executed and the same is followed for the second call to inorder(p->link). So this forms a tree

          inorder(p->link) -> coutinfo ->   inorder(p->link) 
             /   ^                                  /   ^     
            V   /                                  V   /      
         inorder()->cout->inorder()              inorder()->cout->inorder()
           .  ^              /  \                  .  ^                /  \
           .  |              .  .                  .  |                .  .
           .  |                                    .  |
   inorder(p->link) //(p->link is NULL)      inorder(p->link) //(p->link is NULL)

Answer 5

The first time I bumped into recursion was with a factorial function. Factorial is a basic function in maths, given a number N, it returns a number equal to the product of all positive integers less than N.

Consider this simple code in C++ which nicely demonstrates recursion.

int fact(int x)
{
    if(x==1)
        return 1;
    x = x*fact(x-1);
    return x;
}

This inputs an integer, and then calls itself after decrementing the integer until the integer is 1, and returns x. Note that the line 'return x;' is not called until the line before it finishes.

Answer 6

Suppose p points to A, p->link (that is, A.link) is called q and points to B, and q->link (which is to say B.link) is NULL, call it r.

  p      q      r
----->A----->B----->0

Now we call inorder(p).

1. p is not NULL, so inorder(p) calls inorder(q) (step 1)
2. q is not NULL, so inorder(q) calls inorder(r) (step 1)
3. r is NULL, so inorder(r) skips the block and returns control to inorder(q)
4. inorder(q) prints B.info (step 2)
5. inorder(q) calls inorder(r) (step 3) which again returns control to inorder(q), which returns control to inorder(p)
6. inorder(p) prints A.info (step 2)
7. inorder(p) calls inorder(q) (step 3), which runs through 2-5 again (printing B.info again), then inorder(p) returns control to whatever called it.

Answer 7

Before the "control goes back to the same function" in step 1, CPU makes an important step: it marks the place in code of inorder where it needs to restart execution once "the second level" of inorder returns (that's the spot right after step 1). There, the "second level" marks the return position again before going to the "third level", the "fourth level", and so on. Eventually, the N-th level gets a NULL, so it returns right away. Then the N-1-th level gets to print the info, and proceed to call inorder for the second time. Now the return location is different - it's right after step 3. Once N-th level finishes, N-1-st level finishes as well, going back to N-2-nd level, then to N-3-rd, and so on, until the very first level exits.

Here is an example tree:

      A
    /   \
   B     C
       /   \
      D     E

The process of inorder traversal goes like this:

inorder(A)            -- step 1, level 1
  inorder(B)          -- step 1, level 2
    inorder(NULL)     -- returns
    cout << B         -- step 2, level 2
    inorder(NULL)     -- returns
  return              -- level 2 returns 
  cout << A           -- step 2, level 1
  inorder(C)          -- step 3, level 2
    inorder(D)        -- step 1, level 3
      inorder(NULL)   -- returns
      cout << D       -- step 2, level 3
      inorder(NULL)   -- returns
    return            -- level 3 returns
    cout << C         -- step 2, level 2
    inorder(E)        -- step 1, level 3
      inorder(NULL)   -- returns
      cout << E       -- step 2, level 3
      inorder(NULL)   -- returns
    return            -- level 3 returns
  return              -- level 2 returns
return                -- level 1 returns

Answer 8

you should learn about call stack if you want to understand how the recursion works. Here is the link. Hope this will help...