C++ recursion example explanation

Question

I have the following code example and I cannot figure out why it displays 123. Since these are integers I understand the decimals are not displayed. But I expected it to show 3, 2(.3), 1(.23) (in the opposite order). When n goes below 10 everything stops after the final cout... right?

#include <iostream>
using namespace std;
void recursion(int n)  {
    if (n < 10)  cout << n;
    else  {
        recursion(n / 10);
        cout << n % 10;
    }
}

int main()  {   
  recursion(123);
  return 0;
}

Try moving the cout << n % 10; to before the recursive call... ;) — Some programmer dude
– Some programmer dude, Commented Nov 23, 2014 at 16:17
@Joachim Pileborg I did and 321 :) But I still can't figure out why — Thomas
– Thomas, Commented Nov 23, 2014 at 16:20

Christophe · Accepted Answer · 2014-11-23 16:32:08Z

5

Well, you call with 123 as n, the function executes the statement:

if (n < 10)      // its false, so it continues with else:  
else {
   recursion ( n /10 )  // recursive call n/10 = 123/10 = 12 (as it's int) 
...

It will continue like this, recursively calling with n being 12

    recursion (n/10)      // second recursion call n=12, so n/10 = 1

then the function is executed, with n being 1 so smaller than 10

        if (n < 10)      // its true 
            cout << n;   // 1 gets printed
        else             // no, the rest is skiped  
        ...

then it returns from recursion. So we're back in the context where n was 12. The next statement to be executed in that context is :

    cout << n %10;    //  prints 12 % 10, which is 2

then, continuing like this, similarly it will print 123%10, which is 3. In conclusion, the 123 that is printed has nothing to do with the 123 entered as input.

I think you wanted to do :

...
else  {
    cout << n % 10;       // first print to see the count down
    recursion(n / 10);    // then recurse 
}

But you have to learn using a debugger. As long as you don't, put some extra cout to visualize what's happening.

edited Nov 23, 2014 at 16:32

answered Nov 23, 2014 at 16:15

Christophe

75.1k7 gold badges87 silver badges182 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Thomas Over a year ago

Hmm ok! So when n = 123 reaches recursion(123 / 10), the program won't forget about n = 123. It will simply just try to satisfy the IF statement by dividing down numbers before it finally can start cout << n % 10 statements for each dividing result.. ? (If that question makes any sense. If it doesn't, thanks for the help, things are a bit clearer now!)

Christophe Over a year ago

Yes ! That's it. At each recursion, the function is executed again, but with its own parameters and local variables. This is done with stack memory. When the function returns, all its local context is removed from stack, and the context of the calling function is restored to the state before the call (if parameters are passed by value).

Christophe Over a year ago

Here a link with some additional explanations (and a nice graphic of recursive exececution): sourcecodemania.com/recursion-in-cpp

Collectives™ on Stack Overflow

C++ recursion example explanation

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related