Fibonacci: How to think recursively

[News123]

On 08/29/2010 01:12 AM, Baba wrote:
> 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:
> 
> my attempted rough code:
> 
> def fibonacci(n):
>     # base case:
>         result = fibonacci (n-1) + fibonacci (n-2)
>>> this will end up in a mess as it will create overlapping recursions
> 
> OR
> 
> def fibonacci(n):
>     # base case:
>         fibonacci(n+2) - fibonacci(n+1) - n = 0
>>> this too would create overlapping recursions
> 
Hi Baba,

Let's take another example: factorials:
Trivial, but you 'just have to apply the same techniques FIbonacci


n! = 1 * 2 * 3 . . . * n

Very first thing is to always find a trivial case, or the terminal
condition.
Tjis is, when you reduced the problem to the most trivial case(s), for
which you don't need anymore recursion

for factorials this would be
0! = 1
for Fibonacci you might have multiple trivial cases

and the recursive definition of factorial is\
n! = (n - 1) * n

so the code for factorial looks something like:


def factorial(n):
  if n == 0:
      # treat the trivial case / cases for which ou know the answer
      return 1
  else:
      # reduce the problem by the recursive definition
      return factorial(n-1)*n


Hope this helps.