Chapter 6: Recursion

Chapter 6: Recursion

Type C: Programming Practice/Knowledge based Questions

1. Write a function that takes a number and tests if it is a prime number using recursion technique.

def primeOrNot(num,n):
    if n>=2:
        if (num%n)==0:
            return False
        else:
            return primeOrNot(number,n-1)
    elif num==1:
        return False
    else:
        return True
        
number=eval(input("Enter a number: "))

if primeOrNot(number,number-1):
    print("The number is a prime number")
else:
    print("The number is not a prime number")

2. Implement a function product() to multiply 2 numbers recursively using + and - operators only.

def product( x , y ): 
    # if x is less than y swap 
    # the numbers 
    if x < y: 
        return product(y, x) 
      
    # iteratively calculate y 
    # times sum of x 
    elif y != 0: 
        return (x + product(x, y - 1)) 
      
    # if any of the two numbers is 
    # zero return zero 
    else: 
        return 0
  
# Driver code 
x = int(input("Enter 1st number: "))
y = int(input("Enter 2nd number: "))
print( product(x, y))

3. The hailstone sequence starting at a positive integer n is generated by following two simple rules. If n is even, the next number in the sequence is n/2. If n is odd, the next number in the sequence is 3*n + 1. Repeating this process, the hailstone sequence gets generated. Write a recursive function hailstone(n) which prints the hailstone sequence beginning at n. Stop when the sequence reaches the number 1 (since otherwise, we would loop forever 1, 4, 2, 1, 4, 2, ...)

def hailStone(n):
    if n%2==0:
        n=int(n/2)
        print(n,end=" ")
    else:
        n=int(3*n+1)
        print(n,end=" ")
    while(n!=1):
        hailStone(n)
        break
n=int(input("Enter a number: "))
hailStone(n)

4. A happy number is a number in which the eventual sum of the square of the digits of the number is equal to 1.

Write a program that takes a number and checks if it is a happy number by using following two function in it:

sum_sq_digits: returns the sum of the square of the digits of the number x, using the recursive technique

ishappy(): checks if the given number is a happy number by calling the function syn_sq_digits and displays an appropriate message

def ishappy(num):
    if num=='7' or num=='1':
        output=1
    else:
        output=sum_sq_digits(num,len(num))
    if output==1:
        print("The number",num,"is a happy number")
    else:
        print("The number",num,"is not a happy number")
def sum_sq_digits(numb,n):
    sum=0
    if(len(numb)>1):
        
        for i in range(0,n):
            sum=int(numb[i])**2+sum
        if sum==1:
            return sum
        sum=str(sum)
        return sum_sq_digits(sum,len(sum))
    else:
        return 0
    
number=str(input("Enter a number: "))
ishappy(number)

5. A list namely Adm stores admission numbers of 100 students in it, sorted in ascending order of admission numbers. Write a program that takes an admission number and looks for it in list Adm using binary search technique. The binary search function should user recursion in it.

def binSearch(lst,key,start,end):
    if start>end:
        return -1
    mid=int((start+end)/2)
    if key==lst[mid]:
        return mid
    elif key=0:
    print(admNumber,"Found at index",result)
else:
    print("Sorry!",admNumber,"NOT FOUND in list")