## DEV Community is a community of 620,905 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Recursive vs Non-Recursive functions

The recursive function for finding the nth term of Fibonacci series took way too much time, before I tried with another array based algorithm.

``````# File fib.py

import time

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

def fib_nr(n):
l = [0,1]
for i in range(1, n):
nn = l + l
l.append(nn)
l = l[1:4]

return l[-1]

n = 30

print("N = %d" % n)
print("-")
t1_start = time.perf_counter()
print("Recursive %d" % fib(n))
t1_stop = time.perf_counter()

t2_start = time.perf_counter()
print("Non-Recursive %d" % fib_nr(n))
t2_stop = time.perf_counter()

t1 = (t1_stop-t1_start)
t2 = (t2_stop-t2_start)

print("-")
print("Elapsed Time for fib() %.6f s" % t1)
print("Elapsed Time for fib_nr() %.6f s" % t2)
print("Faster by %.1f" % (t1/t2))

``````

### The benchmark results ?

On my 8GB mac-book air, about 15,000 times faster when n=30!

``````❯❯ python3 fib.py
N = 30
-
Recursive 832040
Non-Recursive 832040
-
Elapsed Time for fib() 0.566854 s
Elapsed Time for fib_nr() 0.000037 s
Faster by 15233.1
`````` ## Discussion (0) 