A twist in Fibonacci's sequence in Python

Question

I am studyng recursion in Python and now I am having a problem with this exercise:

Remember that Fibonacci's sequence is a sequence of numbers where every number is the sum of the previous two numbers.

For this problem, implement Fibonacci recursively, with a twist! Imagine that we want to create a new number sequence called Fibonacci-3. In Fibonacci-3, each number in the sequence is the sum of the previous three numbers. The sequence will start with three 1s, so the fourth Fibonacci-3 number would be 3 (1+1+1), the fifth would be 5 (1+1+3), the sixth would be 9 (1+3+5), the seventh would be 17 (3+5+9), etc.

Name your function fib3, and make sure to use recursion.

The lines below will test your code.

If your function is correct, they will print 1, 3, 17, and 57.

print(fib3(3))
print(fib3(4))
print(fib3(7))
print(fib3(9))

This is the code until now:

def fib3(n):
    if n <= 1:
        return n
    else:
        return(fib3(n-1) + fib3(n-2) + fib3(n-3))

But the results are: 1, 2, 11, 37

Can you help me please to correct it?

Answer 1

Let me contribute with perhaps the most optimal "pythonic" answer.

The main point is to avoid recursive function calls to optimise the efficiency of the code. Pythonic way of thinking would involve the following compact code, which is an iterative creation of the Fibonacci sequence of n numbers, including the seed numbers [1, 1, 1].

def fibonacci_sequence(n):
    x = [1, 1, 1]
    [x.append(x[-1] + x[-2] + x[-3]) for i in range(n - len(x))]
    return x

import time
n = int(raw_input("Enter the size of Fibonacci-3 sequence: "))
start_time = time.time()
print fibonacci_sequence(n)
print "The time to compute the Fibonacci-3 sequence is: %s" % (time.time() - start_time)

Answer 2

The same thing other people are saying

As others have noted, you have to return 1 when n <= 3

def fib3 (n):
  if n <= 3:
    return 1
  else:
    return fib3(n - 1) + fib3(n - 2) + fib3(n - 3)

print(fib3(3)) # 1
print(fib3(4)) # 3
print(fib3(7)) # 17
print(fib3(9)) # 57

... but you can do better than that

But that definition of fib3 is junk. It does an insane amount of computation duplication. For example, fib3(40) takes over 30 minutes to compute due to O(n³) complexity

Consider an approach that uses an auxiliary loop with state variables – The O(n) complexity allows it to compute the same result in less than a millisecond.

def fib3 (n):
  def aux (n,a,b,c):
    if n == 1:
      return a
    else:
      return aux(n-1,b,c,a+b+c)
  return aux(n,1,1,1)

print(fib3(3))  # 1
print(fib3(4))  # 3
print(fib3(7))  # 17
print(fib3(9))  # 57
print(fib3(40)) # 9129195487

---

Fibonacci as a generic program: fibx

We can make generic the entire process of generating fibonacci sequences, but first we have to address something with your fib3 function. In general, Fibonacci numbers have a 0th term - ie, fib(0) == 0, fib(1) == 1. In your function, it looks like the first number is fib3(1), where fib3(0) would produce an undefined result.

Below, I'm going to introduce fibx which can take any binary operator and any seed values and create any fibonacci sequence we can imagine

from functools import reduce

def fibx (op, seed, n):
  [x,*xs] = seed
  if n == 0:
    return x
  else:
    return fibx(op, xs + [reduce(op, xs, x)], n - 1)

Now we can implement standard fibonacci using fibx with the add (+) operator and seed values 0,1

from operator import add

def fib (n):
  return fibx(add, [0,1], n)

print(fib(0)) # 0
print(fib(1)) # 1
print(fib(2)) # 1
print(fib(3)) # 2
print(fib(4)) # 3
print(fib(5)) # 5

Implementing fib3 using fibx

We can use the same fibx with the add operator to implement your fib3 function, but because of your 1-based index, notice I'm offsetting n by 1 to get the correct output

from operator import add

def fib3 (n):
  return fibx(add, [1,1,1], n-1)

print(fib3(3)) # 1
print(fib3(4)) # 3
print(fib3(7)) # 17
print(fib3(9)) # 57

I'd recommend you start with a 0-based index tho. This means 0-based index fib3(2) is actually equal to your 1-based index of fib3(3)

from operator import add

def fib3 (n):
  return fibx(add, [1,1,1], n)

print(fib3(2)) # 1
print(fib3(3)) # 3
print(fib3(6)) # 17
print(fib3(8)) # 57

Any imaginable sequence using fibx

And of course you can make any other sequence you can imagine. Here we make weirdfib that uses multiplication (*) instead of addition (+) to combine terms and has a starting seed of [1,2,3]

from operator import mul

def weirdfib (n):
  return fibx(mul, [1,2,3], n)

print(weirdfib(0)) # 1
print(weirdfib(1)) # 2
print(weirdfib(2)) # 3
print(weirdfib(3)) # 6
print(weirdfib(4)) # 36
print(weirdfib(5)) # 648
print(weirdfib(6)) # 139968

Answer 3

Your problem description tells you why:

The sequence will start with three 1s

Your solution, however only returns 1 for n == 1 or lower:

if n <= 1:
    return n

This means that for n == 2 (which should still return 1), you'd instead return fib3(2-1) + fib3(2-2) + fib3(2-3), or fib3(1) + fib3(0) + fib(-1), which thanks to the above test, then bottoms out to produce 1 + 0 + -1 == 0.

For n == 3, you'd return fib3(2) + fib3(1) + fib3(0); we worked out above that fib3(2) is 0, so the end result is 0 + 1 + 0 is the 1 you observed.

Finally, the 4th fib3 number (n == 4), does not return 3, but fib3(3) + fib3(2) + fib3(1) == 1 + 0 + 1 == 2.

Change that first test return 1 for n <= 3, to fix those first 3 values in the series:

def fib3(n):
    if n <= 3:
        return 1
    else:
        return fib3(n-1) + fib3(n-2) + fib3(n-3)

Now the code passes the given tests:

>>> def fib3(n):
...     if n <= 3:
...         return 1
...     else:
...         return fib3(n-1) + fib3(n-2) + fib3(n-3)
...
>>> print(fib3(3))
1
>>> print(fib3(4))
3
>>> print(fib3(7))
17
>>> print(fib3(9))
57

Answer 4

If n <= 1, the situation is a little more complex than just return n.

Consider the case of n = 4: your recursive call will be fib(3), fib(2), and fib(1).

The lattermost returns 1 immediately, which is what you want. However, the two recursive calls do some weird things. fib(2) recurses into fib(1), fib(0), and fib(-1), the return values for which basically hand back a big fat 0. fib(3) recurses into fib(2) (which we saw is 0), fib(1) (which works, and is 1), and fib(0) (which is also 0).

Hence, you get the 1 from the very beginning, and the 1 from the recursed fib(1) component of fib(3). There's your 2!

Basically, you want to make sure your base case can't return a negative number. Fix that (return either 1 or 0), and you should be good. As Martijn Pieters mentioned, you can also make your base case n <= 3 and it should achieve the same effect.