Is there anyway to get a recursive function to use less processing power and time

Question

This function can’t take an input larger than 33 without causing a runtime error. Is there a way to improve it?

https://code.sololearn.com/cjDCAogC8U0q/?ref=app

Answer 1

Simple: Don't use recursion, use memoization instead. Oma Falk

fib_cache = {}

def fibonacci(n):
if n in fib_cache:
return fib_cache[n]

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

fib_cache[n] = val
return val

for i in range(int(input())):
print(i, fibonacci(i))

Answer 2

Another way is to use tail recursion: it's similar to memoization, but instead of storing the values in an external cache, you store them in function parameters.

Here's an example:
https://code.sololearn.com/cxYxe99a1F1p/?ref=app

Answer 3

Why not use a simple for loop:

# create n fibonacci numbers

fib = [0, 1]
inp = int(input('Number fibonacci values: '))
for i in range(inp -2):
fib.append(fib[len(fib) -1] + fib[len(fib) -2])
print(fib)
# or print only last element
print(fib[-1])

Answer 4

Yes use an array to store the Fibonacci values of smaller indices.