1
$\begingroup$

I need help with this recursion question:

help

  • 6
    Did you try coding it up? Your profile says you know Java and C...2010-12-11
  • 0
    i didnt even think of doing that2010-12-11
  • 0
    damn i dont have .net at my house2010-12-11
  • 0
    Try calculating the first few values by hand. You should notice a pattern...2010-12-11
  • 5
    A small lie plus a mispronounced potato flour pasta perhaps?2010-12-11
  • 3
    @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:  ”2010-12-11
  • 0
    @NEWprogrammer Convert it to some language for which you *do* have a compiler, then.2010-12-11
  • 0
    This looks a very creative recursion for Fib-series,since it doesn't follow the standard recurrence.2010-12-11
  • 0
    Over 90% of all recursion homeworks are algorithms for Fibonacci numbers. 2010-12-13

2 Answers 2

7

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!

  • 0
    so it would be 0 is current then I would get 0 1 is current then I would get 1 2 is current then i would get 3 3 is current then i would get 4?2010-12-11
  • 0
    sorry this is the last homework of the semester and i am on the edge of a c and a b and its worth 130 points2010-12-11
  • 0
    When the function is called from within itself, you need to keep track of both the first _and_ the second parameter that are passed to it.2010-12-11
  • 0
    isnt that what i dide because if i use 0 as the start 0 + last(0) = 02010-12-11
  • 0
    but 1+ last(0) = 1 and 2 + last(1) = 32010-12-11
  • 2
    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.2010-12-11
  • 3
    @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.2010-12-11
  • 0
    the answer is just plainly 1, right?2010-12-11
  • 0
    because i am starting with both 0 and 12010-12-11
  • 0
    @Brandon I wasn't talking about an abstract situation in life, I was talking about this particular homework. Its aim is clearly to give students a feel for recursion and I believe that the best way to do that is to understand the code, rather than recognise a familiar sequence in the output. If the teacher had wanted to achieve the latter, he would have given them the code in some existing programming language, ready to run on a computer, rather than pseudo-code.2010-12-11
  • 0
    @Brandon By the way, me being a mathematician, I do exactly what you are describing all the time. I run numerical experiments, formulate conjectures, then go away and prove them. But this is a totally different situation.2010-12-11
  • 0
    i agree this homework isn't testing my ability to write vb code or c, its about understanding it correctly and at this point i dont get it2010-12-11
  • 0
    was i right about it being 12010-12-11
  • 0
    @NEWprogrammer You are not giving particularly useful feedback. Have you done what I recommended you to do? Have you computed 4 or more iterations? What are the pairs of parameters in the first iterations? Have you tried describing the program in words? "I don't get it" is not terribly useful for me as someone who is trying to help you. In the last comment, I have no idea what you mean by "it".2010-12-11
  • 1
    i plugged in 1 for the current and 0 for the last, and got 1. then i plugged in 2 for the current and 1 for the last and got 3. Then i plugged in 3 for the current and 2 for the last and got 5.2010-12-11
  • 0
    @NEWprogrammer That sounds much better. So if the $n$-th iteration is called with parameters (a,b), then what are the parameters for the $(n+1)$-st iteration?2010-12-11
  • 0
    hmmm well according to the question they are useing 0,1 as there parameters and then it should be 0+1 = 1, i believe2010-12-11
  • 0
    @NEWprogrammer Your fourth iteration was called with parameters (2,3). What will the parameters for next one be? If you know the parameters for the $n$-th iteration, how do you determine the parameters for the $(n+1)$-st iteration? _Please_ think about it for a couple of minutes before posting. _Please_!2010-12-11
  • 0
    if 3<100 then temp<- 3+2 = 5 apply mystery write (3,5)2010-12-11
  • 1
    So can you now answer my question? If I told you that the 20-th iteration will be called with parameters (50,62), can you tell me what the 21-st iteration will be?2010-12-11
  • 0
    if 50<100 then temp <- 50+ 12=62 apply mystery write (50,62), i think2010-12-11
  • 2
    @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.2010-12-11
  • 3
    1 1 2 3 5 8 13 21 34 55 892010-12-11
  • 1
    They used to give a first years' course where every single weekly exercise sheet come back to these numbers.2010-12-11
1

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