Help once again with recursion

[-TesseracT-]

I shall find the sum of all the even Fibonacci numbers under 4 million. What I don't understand is exactly how Fib(i) relates to the second method (int fib(int f)) I know the code works, but it was I wild guess. I don't know exactly what's going on and I need to comment the code.

[-TesseracT-]

My teacher told me that I should only run Fib(i) once. I don't get it.

[TideRower]

My teacher told me that I should only run Fib(i) once. I don't get it.

It would be faster to just call Fib(i) before the if statement and save its result. Right now every even Fibonacci-number gets calculated twice.

The second method just gives you the i.th Fibonacci-number using recursion.

If you don't understand what it does just write down what happens for a small i, i.e i=4:

Fib(4) = Fib(3) + Fib(2)

Fib(3) = Fib(2) + Fib(1)

Fib(2) = 1     Fib(1) = 1

hence Fib(4) = 1 + 1 + 1 = 3

[beingGamer]

My teacher told me that I should only run Fib(i) once. I don't get it.

 

The basic idea behind recursion is calling a function only once from your main program.

and then the function keeps calling itself with new values.

 

So you have to modify your program to follow above idea.

Keep all the calculation & iteration stuff in the function and just call it from your main program.

 

you might run into some infinite loops at times while developing it

[-TesseracT-]

Ok guys I though I understood but apparently don't. Could someone just finish the program for me?

[Ciccioo]

Could someone just finish the program for me?

no

 

beware: the recursive approach to the fibonacci series is very slow: to compute the Nth number, the function recursively calls itself 2^N times, which takes seconds just to compute Fib(40), thousands of years for Fib(1000000). it will also eventually cause a stack overflow when it hits the recursion limit at around Fib(100000)

 

search google for methods to compute the fibonacci numbers using memoization. this way, each fibonacci number gets calculated with just one operation instead of recursing for days and days

[asquirrel]

I shall find the sum of all the even Fibonacci numbers under 4 million. What I don't understand is exactly how Fib(i) relates to the second method (int fib(int f)) I know the code works, but it was I wild guess. I don't know exactly what's going on and I need to comment the code.

The way fib(i) relates to ( int fib(int f) ) is that i is the value passed to the function as the variable f within that function. 

 

As for how recursion itself works...say you called fib(4) (where 4 is the value of i) then this is how recursion would handle that (color coding added to show which function calls correspond to which and which are duplicated, but non-matching function calls):

 

Thus, the end result of calling Fib(4) would be 5. Without doing your work for you, this is about the best way I can explain how recursion works. Something a drunk college frat boy once told me about programming: When you're confused, draw pictures until it makes sense. I have to give him credit, that advice has worked every time.