Reputation: 17

Recursion in c++

I got an exam two days from now and my professor gave us an old exam with the solutions however after going over this problem countless of times I can't figure out how in the world the answer is the answer.

int recursive (int n) {
    if (n < 10) return n;
    return 100 * recursive (n / 100) + 10 * (n % 10);
}
int main(){
    cout << recursive (19683) << endl;
    return 0;
}

The answer should print out 16030 but I have no idea of how it gets that. I do

100*196+10*3 = 19630

Then I do

100*1+10*3 = 130

which is completely wrong would appreciate it if someone knew how to get to that answer

Upvotes: 0

Answers (4)

Patashu

Reputation: 21773

Back in high school we were taught to be able to desk check our code. Desk checking is where you compute, by hand, the result of every step.

int recursive (int n) {
    if (n < 10) return n;
    return 100 * recursive (n / 100) + 10 * (n % 10);
}

Pass this 19683

recursive(19683)

19683 < 10 is false

return 100 * recursive(196) + 10 * (19683 % 10 -> 3)

recursive(196)

196 < 10 is false

return 100 * recursive(1) + 10 * (196 % 10 -> 6)

recursive(1)

1 < 10 is true, return 1

substitute recursive(1) = 1 into earlier equation...

return 100 * 1 * 60 -> 160

substitute recursive(196) = 160 into earlier equation...

return 100 * 160 + 10 * 3 -> 16030

Upvotes: 1

TheDarkKnight

Reputation: 27611

In order to understand what's happening, look at a a simpler example of recursion, such as reversing a string. There's a good explanation of how recursion works in the answers to this question: -

Reverse a string using recursion

Once that makes sense to you, you should find understanding the example question you pose much easier.

Upvotes: 0