Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I need help with this recursion question:


share|cite|improve this question
Did you try coding it up? Your profile says you know Java and C... – Aryabhata Dec 11 '10 at 4:55
i didnt even think of doing that – NEWprogrammer Dec 11 '10 at 4:56
damn i dont have .net at my house – NEWprogrammer Dec 11 '10 at 4:59
A small lie plus a mispronounced potato flour pasta perhaps? – Jon Beardsley Dec 11 '10 at 5:03
@JBeardz: horribly, horribly mispronounced — but good hint :-) And while being flippant, since images aren’t shown in the snippets of questions on the front page, this question appeared there as: “Homework question dealing with recursion: I need help with this recursion question: ” – Peter LeFanu Lumsdaine Dec 11 '10 at 5:50
up vote 7 down vote accepted

Don't code it! Instead compute the first 4 or so values by hand and see if you understand what is going on. You don't even have to look at the numbers, you just need to see what you are doing when you evaluate the code. E.g. try to say in words what you do when you follow the code. Pretend that you are explaining the program to a friend: "so this thing first checks whether the second parameter is less than 100..."

If you don't see what you are doing, then do some more iterations (by hand) and look at the numbers, you will easily recognise them. If you don't recognise them, please leave a comment here, telling us what the numbers are.

But let me repeat: if you want to practice reading code, try to understand what you are doing, rather than guess a pattern from the numbers. Therefore, do not code it!

share|cite|improve this answer
You are not reading the code carefully. In the first iteration, last=0, current=1. In the second iteration, the value of last becomes that of current, so 1, the value of current becomes last+current=0+1=1. Repeat at least four times, see what you get. Please take longer than 30 seconds to actually verify your answer, before you post another comment. – Alex B. Dec 11 '10 at 5:09
@Alex: I disagree with the notion to not code the algorithm, in general. For an example like this, where the pattern is very plainly visible in the code, it is a good idea to not have to lean on coding it as a crutch. If you have more obfuscated code, I think it's often helpful to see if you can recognize a pattern in the output, then go back and see if you can prove that the code does exactly what you think it does. – Brandon Carter Dec 11 '10 at 5:09
@NEWprogrammer I have implored you in vain to think for some minutes before posting comments. My last advice is: after you answer my previous question (correctly), try to write down a rule for how to produce the sequence of successive values of Current. Make sure that the sequence that your rule produces matches up with your previous calculations. If you can produce the sequence, you will have solved the exercise. I am leaving you alone with this now. – Alex B. Dec 11 '10 at 5:57
1 1 2 3 5 8 13 21 34 55 89 – NEWprogrammer Dec 11 '10 at 6:00
@Alex Bartel: +1 for your heroic efforts! It seems they paid off. – TonyK Dec 11 '10 at 14:24

HINT $\ \ $ Show the sequence of Current values has form $\rm\ 1,\ 1,\ 2,\ \cdots\ a,\ b,\ a+b$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.