Chapter 05: Induction and Recursion

Example 01: Page 346

In [1]:
#to compute the recursive functions
def f(n):

    if n==0:
        return 3
        result=2*f(n)+3 #recursive call
        return result
for num in range(1,5):
    print "The value of f(",num,") is",r #Prints the result for individual instance
The value of f( 1 ) is 9
The value of f( 2 ) is 21
The value of f( 3 ) is 45
The value of f( 4 ) is 93

Example 01: Page 361

In [2]:
#To compute the factorial of a given number using recursion
def factorial(n):
    if n==0:
        return 1
        return n*factorial(n-1) #recursive function call
num=input("Enter a number whose factorial is to be found");
print "The factorial of",num,"is",factorial(num);
Enter a number whose factorial is to be found4
The factorial of 4 is 24

Example 02: Page 361

In [3]:
#To compute power using recursive algorithm
def power(a,n):
    if n==0:
        return 1
        return a*power(a,n-1) #recursive call algorithm
num=input("Enter the number");
p=input("Enter the power");
print "The value of",num,"to the power",p,"is",power(num,p);
Enter the number5
Enter the power4
The value of 5 to the power 4 is 625

Example 03: Page 362

In [5]:
#To compute gcd using modular recursion
def gcd(a,b):
    if a==0:
        return b
        return gcd(b%a,a) #recursive call

num1=input("Enter the first number")
num2=input("Enter the second number")
print "The gcd of",num1,",",num2,"is",gcd(num1,num2)
Enter the first number5
Enter the second number8
The gcd of 5 , 8 is 1

Example 04: Page 362

In [4]:
#To compute mpower function using recursion
def mpower(b,n,m):
    if n==0:
        return 1
        if n%2==0:
            return ((mpower(b,n/2,m))**2) % m #recursive call
            return ((mpower(b,n/2,m)**2)%m*(b%m))%m #recursive call
number=input("Enter the number")
power=input("Enter the power")
modulo=input("Enter the modulo number");
print "The answer of mpower(",number,",",power,",",modulo,") is",mpower(number,power,modulo)
Enter the number2
Enter the power5
Enter the modulo number3
The answer of mpower( 2 , 5 , 3 ) is 2

Example 09: Page 367

In [5]:
def msort2(x): #function for merge sort
    if len(x) < 2:
        return x
    result = []          
    mid = int(len(x)/2) #divides the elements into halves
    y = msort2(x[:mid])
    z = msort2(x[mid:])
    while (len(y) > 0) and (len(z) > 0):
            if y[0] > z[0]:
                result.append(z[0]) #merges to append the elements
    result += y
    result += z
    return result
l=raw_input("enter the numbers to be merge sorted").split(",")
print "Ther Merge sort is", r
enter the numbers to be merge sorted8,2,4,6,9,7,10,1,5,3
Ther Merge sort is ['1', '10', '2', '3', '4', '5', '6', '7', '8', '9']