Fibonacci in python, recursively into a list

Question

I am practicing with some code, and one thing I am trying to do is have the Fibonacci sequence placed recursively into a list. I have managed to do it without recursion, but that is not too difficult. Thank you to anyone who can offer any help.

#python 2

arr = [1, 1]
n=15
def Fib(n):
  tmp = arr[-1] + arr[-2]
  if n == 0:
    return 0 #base case 1
  elif n == 1:
    return 1  #base case 2
  else:
    return Fib(n-1) + Fib(n-2) #recursive call
  arr.append(tmp)
  return arr
Fib(n)
print arr

please tell us more about how you are trying to attempt this, what result(s) you have so far and any error message or difficulties you are encountering...thanks — glls, Jun 14 '16 at 02:47

Priyansh Goel · Accepted Answer · 2016-06-14T03:07:33.530

Do a dry run of your code. You will find that

arr.append(tmp)
  return arr

The above code never gets executed as it returns the answer before in one of the if-else conditions.

The following code helps:

arr = []
n=15
def Fib(n):

  if arr[n] != -1:
    return arr[n]
  if n == 0:
    arr[0] = 0
    return 0 #base case 1
  elif n == 1:
    arr[1] = 1;
    return 1  #base case 2
  else:
    arr[n] = Fib(n-1) + Fib(n-2);
    return arr[n];

for i in range(n+1):
    arr.append(-1);
Fib(n)
print arr

What I am doing is that initially I am assigning -1 to all the indexes in the list telling that this particular state has never been visited. Once, I visit a particular state, I store its solution in the arr at that index. And if the solution state has been visited and is encountered again, I straight away return the solution possible at that index without recursing further on it.

do you know of a way where arr=[] could be within the function? — amitnair92, Jul 19 '21 at 08:28

score 1 · Answer 2 · answered Jun 14 '16 at 02:58

In Python 3 you can do an efficient recursive implementation using lru_cache, which caches recently computed results of a function:

from functools import lru_cache

@lru_cache(100)
def fib(N):
    if N <= 1:
        return 1
    return fib(N - 1) + fib(N - 2)

[fib(i) for i in range(10)]
# [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

This also works without the cacheing, but computational complexity is exponential in N for that case.

score 0 · Answer 3 · answered Jun 14 '16 at 02:51

0

faster way

def Fib():
    a,b = 0,1
    yield a
    yield b
    while True:
        a, b = b, a + b
        yield b

from itertools  import islice 

for i in islice(Fib(),15):
    print i

answered Jun 14 '16 at 02:51

galaxyan

5,527
2
18
41

This doesn't answer the question. (It doesn't use recursion at all.) – user94559 Jun 14 '16 at 02:53

user94559 · Answer 4 · 2016-06-14T03:06:01.157

0

Here's one solution:

def fib(n, sofar=[]):
  if n == 0:
    return sofar

  if len(sofar) < 2:
    return fib(n-1, sofar + [1])

  return fib(n-1, sofar + [sofar[-1] + sofar[-2]])

print(fib(11))

edited Jun 14 '16 at 03:06

answered Jun 14 '16 at 02:53

user94559

57,357
6
98
99

score 0 · Answer 5 · answered Jun 14 '16 at 04:19

You could also do it like this:

    def fibonacci(n):
        if n == 0:
            return 0
        elif n == 1:
            return 1
        else:
            return fibonacci(n-2) + fibonacci(n-1)

    number = int(input("Enter the range of numbers: "))

    result = []
    start = 1
    for num in range(start, number+1):
        result.append(fibonacci(num))
    print(result)

    # Output
    [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

score 0 · Answer 6 · answered Jun 14 '16 at 04:51

Try the following recursive method.

# Where 'n' is the max range of a number in Fibonacci series 
def fibo(n, a = 0, b = 1, fib = []):
    if b < n:
        fib.append(b)
        a, b = b, a + b
    else:
        return fib
    return fibo(n, a, b, fib)


print fibo(20)

Output

[1, 1, 2, 3, 5, 8, 13]

Fibonacci in python, recursively into a list

6 Answers6

Linked