CODEWITHSUNDEEP
c++recursiondata-structuresrecursive-datastructures
Zack Maguffin
Zack Maguffin

Reputation: 45

C++ Recursive Final Exam Review

While studying for my upcoming final exam I came across this review question, I know the answer when I call test_b(4) is: 0 2 4. My question is why it prints the 2 and 4 after the 0 if the first test_b(n - 2) comes before the cout?

void test_b(int n)
{
   if (n>0)
      test_b(n-2);
   cout << n << " ";
}

Upvotes: 2

Views: 403

Answers (6)

molbdnilo
molbdnilo

Reputation: 66459

Recursive functions work exactly like all other functions.
(I think this is the most crucial thing to understand about recursion.)

So, let's get rid of the recursion by specialising the function into several.

These functions are equivalent to your "recurse first" implementation:

void testb_0()
{
    cout << 0 << " ";
}

void testb_2()
{
    testb_0();
    cout << 2 << " ";
}

void testb_4()
{
    testb_2();
    cout << 4 << " ";
}

and these are equivalent to your "print first" implementation:

void testa_0()
{
    cout << 0 << " ";
}

void testa_2()
{
    cout << 2 << " ";
    testa_0();
}

void testa_4()
{
    cout << 4 << " ";
    testa_2();
}

I'm convinced that you understand how these are different.

Upvotes: 1

Ziezi
Ziezi

Reputation: 6467

Because it reaches the print statement only when the if statement is false, i.e. n <= 0. After that it prints the values of n backwards, with respect to the recursive calls.

Perhaps it would be more clear if the code is presented like so:

void test_b(int n)
{
   if (n > 0)
   {
       test_b(n - 2); // II: execution resumes from here for the rest n's
   }

   cout << n << " ";  // I: this line is reached first when n <= 0  
}

Upvotes: 2

Adrian Maire
Adrian Maire

Reputation: 14865

Think about calls in a V shape:

 test_b(4)
  | //>0, so enter the if
  |  test_b(2)
  |   | //>0 so enter the if
  |   |  test_b(0)
  |   |   | //==0, so skip if
  |   |   | print 0 // from the test_b(0)
  |   |   | return
  |   |  print 2 // from test_b(2)
  |   |  return
  |  print 4 // from test_b(4)
  |  return
// end

The result is shown as printed, first the 0, then the 2, finally 4: 0 2 4.

Upvotes: 4

nwp
nwp

Reputation: 10011

One way to imagine how this works is to do a series of replacements and simplifications.
We start with test_b(4). That can be replaced with the body of test_b, except we replace n with 4.

if (4>0)
   test_b(4-2);
cout << 4 << " ";

We know that 4>0 is true and 4-2 == 2 so we can simplify to:

test_b(2);
cout << 4 << " ";

Then we substitute again:

if (2>0)
   test_b(2-2);
cout << 2 << " ";
cout << 4 << " ";

You can repeat the simplification and substitution steps until you arrive at the final solution.

Upvotes: 0

PMar
PMar

Reputation: 31

Evaluation of test_b(4) generates three nested calls. In the first call, the condition is true, so it makes the second call; in the second call, the condition is true, so it makes the third call. In the third call, the condition is false - at that level n=0 - so it skips directly to the output and prints IT'S value of n, i.e 0. Then the third call returns up to the second call - for which n=2 - and continues to the output and prints 2. Then the second call returns up to the first call - for which n=4 - and continues to the output and prints 4. Then the first call ends.

Upvotes: 3

Bathsheba
Bathsheba

Reputation: 234875

Briefly, nothing is printed until (n > 0) is false, and the recursion block is hit.

You get the output, from 0 and effectively increasing by 2, as the stack unwinds.

A line by line debugger is always helpful when looking at stuff like this.

Upvotes: 3

Related Questions