Need help understanding recursion

Question

So in my class we are studying recursive functions. But I just do not understand how they work.

I'll use this code as an example.

// n is written to the screen vertically
// with each digit on a separate line.

void write_vertical(int n) {

    if (n < 10) 
    {
        cout << n << endl;
    }
    else   // n is two or more digits long
    { 
        write_vertical(n/10);
        cout << (n % 10) << endl;
    }
}

So if int n = 123; it will print each digit on its own line.How does this happen? how does this function work step by step?

Try writing it out (math functions evaluated) by hand to see what's happening. — tmpearce
– tmpearce, Commented Oct 19, 2016 at 0:27
Pencil and Paper ;) , will help on this question . Testing it by giving it random n numbers — amanuel2
– amanuel2, Commented Oct 19, 2016 at 0:29
Your debugger has a feature to let you step through the program. Use it! — Lightness Races in Orbit
– Lightness Races in Orbit, Commented Oct 19, 2016 at 0:34
I tried to upvote @LightnessRacesinOrbit 's comment too many times and broke something. — user4581301
– user4581301, Commented Oct 19, 2016 at 0:36

zondo · Accepted Answer · 2016-10-19 01:23:05Z

3

Testing by random number (13)

Let's take 13 for an example. Well it's not less than 10, so it will execute the else block, and it will immediately execute the function itself with 13/10, which (as an integer) is 1. Now 1 is less than 10, so it will print 1 onto the screen with a new line because of endl. Now it will return back to the previous function call it had (before calling the function again with argument 1) and execute 13%10. 13 modulus 10 is 3, since its remainder becomes 3, with a new line (again because of endl). And voila, you printed the number in a vertical line!

For future

You should use a pencil and a paper, and debug it yourself manually just like we did above. OR even better use a debugger like GDB! This is an excellent quick startup on how to debug with GDB.

edited Oct 19, 2016 at 1:23

zondo

20.4k8 gold badges50 silver badges89 bronze badges

answered Oct 19, 2016 at 0:36

amanuel2

4,6765 gold badges41 silver badges72 bronze badges

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

Comments

Will Ness · Accepted Answer · 2016-10-19 00:44:14Z

1

Recursion is simple. Assume you've already written your function; then use it.

Here it's the other way around - you are trying to figure out what the function does. Just the same, when you call it, it always does the same stuff.

So, in a general case of a number n > 10, what is n/10 (integer division)? It's that number without its last decimal digit.

What's n % 10? It's the number's last decimal digit.

So, your definition reads:

doing_something for a number `n` IS

    doing_it for this number without its last decimal digit 
                         (if there's something left, that is);

    then printing its last decimal digit and a newline after it.

That's all.

answered Oct 19, 2016 at 0:44

Will Ness

71.6k10 gold badges105 silver badges193 bronze badges

Comments

Raindrop7 · Accepted Answer · 2016-10-19 00:56:47Z

1:

if(123 < 10)     // fails
    cout << 123; // skipped
else
{
    recurse(123 / 10); // recurse(12) converted to int
    cout << 123 % 10; // i'll be back here wait
}

2:

if(12 < 10)     // fails
    cout << 12; // skipped
else
{
    recurse(12 / 10); // recurse(1)
    cout << 12 % 10; // wiat I'll be back
}

3:

if(1 < 10)      // succeeds! so now else executed
    cout << 1; // printed

nothing is below until return of functions so we return to 2:

cout << 12% 10; // (12 % 10 = 2) was wating it's its time

continue below: nothing below so return from function 2 to 1:

in 1:

cout << 123 % 10; // it was waiting so now it's its time
cout << 123 % 10; // 123 % 10 = 3

go below: nothing untile the end of function so retrun to main where function was called first time (to the line after the call )

the result: 123

Collectives™ on Stack Overflow

Need help understanding recursion

3 Answers 3

Testing by random number (13)

For future

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Testing by random number (13)

For future

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related