loading...

Recursive vs Non-Recursive functions

awin profile image Awin Abi ・1 min read

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[0] + l[1]
    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

Graph

Discussion

pic
Editor guide