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

def power(a, b):

if (b == 0):

return 1

else:

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

else:

if(b%2 == 0):

v = power(a, b/2)

return v**2

else:

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

else:

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]

memory={0:0,1:1}

print fib (250)

## No comments:

## Post a Comment