Level: beginner
I would like to know how to approach the following Fibonacci problem:
How may rabbits do i have after n months?
I'm not looking for the code as i could Google that very easily. I'm
looking for a hint to put me on the right track to solve this myself
without looking it up.
my brainstorming so far brought me to a stand still as i can't seem to
imagine a recursive way to code this:
Perhaps you need to start with a simpler case to get your head around the
ideas. Let's look at factorial first.
fact(n) = n*(n-1)*(n-2)*(n-3)*...*2*1
Working upwards:
fact(0) = 1 # this is by definition.
fact(1) = 1 # also by definition.
fact(2) = 2*1 = 2*fact(1)
fact(3) = 3*2*1 = 3*fact(2)
....
fact(n) = n*fact(n-1)
So now you have the base case:
if n is 1 or smaller, fact(n) returns 1
and the recursive case:
otherwise fact(n) returns n*fact(n-1)
Now write that as a Python function, and test it to see that it is
correct. Come back once you've got it working satisfactorily.
Now, can you apply the same reasoning to the Fibonacci problem?
What is your base case? You need some way to halt the recursion,
something that *doesn't* make a recursive call.
def fib(n):
if SOME_CONDITION:
return SOME_VALUE
else:
return SOME_RECURSION
is the most basic form you can have. Notice that you must *return*
something. That's basic Python syntax -- if you don't call return, the
function will return the special None object, which is not what you want.
More generally, you could have multiple base cases and multiple recursive
cases, not necessarily one of each. But there must be at least one non-
recursive expression that gets returned, or the recursion can never
terminate.
my attempted rough code:
def fibonacci(n):
# base case:
result = fibonacci (n-1) + fibonacci (n-2)
Mathematically, there is nothing wrong with overlapping recursion. It
will work, and Python can handle it easily.
But in practical terms, it can lead to great inefficiency. In this
example, it should be avoided because it is slow. Very slow. To calculate
the nth Fibonacci number using naive recursion requires *many* calls:
fib(4) # first call
=> fib(3) + fib(2) # three calls
=> fib(2) + fib(1) + fib(1) + fib(0) # seven calls
=> fib(1) + fib(0) + 1 + 1 + 0 # nine calls
=> 1 + 0 + 1 + 1 + 0 = 3
So to get fib(4) = 3 requires nine calls to fib().
This growth function doesn't have a name (as far as I know), but it grows
much faster than fib() itself:
n = 0 1 2 3 4 5 6 ... 35 ...
fib(n) = 0 1 1 2 3 5 8 ... 9227465 ...
calls = 1 1 3 5 9 15 25 ... 29860703 ...
As you can see, the number of calls is also calculable by a recursive
expression R:
R(0) = R(1) = 1
R(n) = R(n-1) + R(n-2) + 1
This is very similar to the Fibonacci recursion, only it grows more
quickly. But I digress...
You can make the recursive version more efficient if you give it a
memory. In the call to fib(5), for example, it ends up calling fib(4)
once, fib(3) twice, fib(2) three times, fib(1) four times, and fib(0)
twice. If it could remember each value once it saw it, it could
potentially save nine calls (out of fifteen). That's a less inefficient
use of recursion. Think about ways to give it a short-term memory.
You can make it even more efficient by giving fib() a long-term cache, so
that each call to fib(5) requires one cache lookup rather than six (or
fifteen) recursive calls. Other than the first time, obviously. This is
called memoisation, but again I digress.
There are other techniques, but this will do to get started.
