Tuesday, July 12, 2011

Some Programs involving Recursion

We can find a^b using recursion.The code is..

def power(a, b):
if (b == 0):
return 1
a=a*power(a, b-1)
return a

print power(3, 9)

We can optimise the above program and reduce the time complexity.
Here is the code for that..

def power(a, b):
if(b == 0):
return 1
if(b%2 == 0):
v = power(a, b/2)
return v**2
v = power(a, (b-1)/2)
return a*v**2

print power(3, 5)

Next we can move on to finding the nth element of Fibonacci series.
For that we have a recursive code..

def fib(n):
if n<2 :
return n

return fib(n-1)+fib(n-2)

print fib(6)

We can optimise the above code using the technique of memorisation.
Then the code will be..

def fib(n):
if not n in memory:
memory[n] = fib(n-1) + fib(n-2)
return memory[n]

print fib (250)

No comments:

Post a Comment