+ 2

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

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

2nd Sep 2019, 3:38 AM
Evan
4 Respuestas
+ 5
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))
2nd Sep 2019, 4:00 AM
Diego
Diego - avatar
+ 4
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
2nd Sep 2019, 4:26 AM
László Ozsvárt
László Ozsvárt - avatar
+ 4
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])
2nd Sep 2019, 11:35 AM
Lothar
Lothar - avatar
+ 3
Yes use an array to store the Fibonacci values of smaller indices.
2nd Sep 2019, 5:23 AM
Sonic
Sonic - avatar