0

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

Improve this question
6
  • Have you tried stepping through it with a debugger? or addding a print statement inside recursive? Commented May 7, 2013 at 4:50
  • Why should the output be 16030? What is your algorithm trying to achieve? Can you provide more examples and add more details to your question? Commented May 7, 2013 at 4:50
  • 4
    Hint: the first iteration is not 100*196+10*3, it's 100*recursive(196)+10*3 ... Commented May 7, 2013 at 4:51
  • 1
    @srikfreak - "Why should the output be 16030?" Because that's what the professor said the output should be! :) Commented May 7, 2013 at 4:58
  • @MarioTheSpoon We're using essentially notepad and the g++ compiler not using an ide :( Commented May 7, 2013 at 15:48

4 Answers 4

Reset to default
3

The first call (recursive(19683)) returns:

100 * recursive(196) + 10*3

The second call (recursive(196)) returns:

100 * recursive(1) + 10*6

The third call (recursive(1)) returns 1 directly. Substituting back, one gets:

100 * (100 * 1 + 60) + 30 = 10000 + 6000 + 30 = 16030

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

Comments

1

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

Improve this answer

2 Comments

I never heard of this step up method. But they way you described it I doing it your way I was able to do several over problems like this. Nice method I wish I learned this in high school lol
@NoobCoder Basically the idea is, for a pure recursive function (has no side-effects and doesn't modify anything else), the value of that recursive function for passing a given value, once you've calculated it to be something, will always be that something. And you can substitute it into earlier calculations. Even if it's not pure you can do it the first time you reach it from the place you reached it from.
1

recursive(19683) = 100 * recursive(196) + 10 * 3

recursive(196) = 100 * recursive(1) + 10 * 6

recursive(1) = 1

Now back-fill the answers

recursive(196) = 100 + 60

recursive(19683) = 100 * 160 + 30 = 16030

Improve this answer

Comments

0

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.