1

I know this is a programming question but it seems to be more on the mathematical side ( recursion ) I was hoping someone would be able to explain it to me since it will probably be on my exam tomorrow.

http://vvcap.net/db/kIcAQxI5nJGOdN_l18Zb.htp

From 1,1 i cannot do it since the answer is 0 and i seem to get 0, -1 since a becomes 0 and b becomes -1....

This would be an absolute massive help if someone could explain to me where i'm going wrong because it will be worth 10 marks in the exam!

user120282
  • 21

1 Answers1

1

Okay, first you call f(1,1). In this case, you have to evaluate the else branch where you have return f(f(a-1,b-1),b-1). Since a=1 and b=1 you can replace these a-1 and b-1 with its actual value 0. This gives you call return f(f(0,0),0). Since there is no assignment of any variable, you can replace these values simultaneously. Now, you have to evaluate this return f(f(0,0),0) in two steps. First you replace f(0,0) by its return value 0. This gives you return f(0,0). Again, since f(0,0) -> 0 you have return 0.

Marc
  • 755
  • Hey thanks! but, if you have 1,2 this would mean your output would be 0,1,1 so how could i compute an answer from these values? thank you so much btw! – user120282 Jan 20 '14 at 23:50
  • You are doing the same evaluations. $f(1,2) = f(f(1-1,2-1),2-1) = f(f(0,1),1)$. Since $f(0,1) = 0$ you get $f(1,2) = f(0,1) = 0$. Does this make sense to you? – Marc Jan 20 '14 at 23:52
  • not really haha sorry. I don't really see how f(0,1)=0 and then you go on from that point so none of it really makes sense :P – user120282 Jan 20 '14 at 23:55
  • Ooooops. I just realised that I read your code a bit wrong (poor resolution). sorry for the confusion. Okay, we have of course $f(0,1) = 1$. Then gives us the following situation: $f(1,2)=f(f(1−1,2−1),2−1)=f(f(0,1),1) = f(1,1) = f(f(1-1,1-1),1-1) = f(f(0,0),0) = f(0,0)$. – Marc Jan 21 '14 at 00:09
  • For $f(2,2) = f(f(2-1,2-1),2-1) = f(f(1,1),1) = f(f(f(1-1,1-1),1-1),1) = f(f(f(0,0),0),1) = f(f(0,0),1) = f(0,1) = 1$ – Marc Jan 21 '14 at 00:11
  • Wow, ok, thanks! the only thing im really unsure off is the final 1-1 since in the other one you stick with the original value which in this case b originally was 2 so why do you do 1-1? and not 1-2 ? – user120282 Jan 21 '14 at 00:13
  • And i follow your 2,2 where u get 1-1,1-1,1-1 until you randomly get the value 1? – user120282 Jan 21 '14 at 00:15
  • This is because you have to do the recursion as often as needed. For example $f(f(1,1),1)$. First we have to evaluate $f(1,1)=f(f(1−1,1−1),1−1)=f(f(0,0),0) = f(0,0)=0$. We can use this fact in our original problem $f(f(1,1),1)$ and replace $f(1,1)$ with $0$. Thus, we get $f(0,1)=1$. – Marc Jan 21 '14 at 00:19
  • So, I have to go. Good luck with your exams! – Marc Jan 21 '14 at 00:24
  • I still don't fully understand where the 1 is coming from in 2,2. The only logical guess i think off is you're doing 2-1 for the final one ? but then there's only 3 sums and they are 1-1, 1-1 and 1-1 =/ it's nearly 1am! but i don't want to go offline till i understand this: D – user120282 Jan 21 '14 at 00:35