24.Example programs using Recursion

1.Print the factorial of a number using recursion
def fact(n):
    if n==0:
        return 1
    else:
        return n*fact(n-1)

n=int(input('Enter n..:'))
x=fact(n)
print("factorial of ..",n ," ..is.. ",x)

output:

Enter n..:5

factorial of .. 5  ..is....120

2.Program to print n’th Fibonacci number

def fib(n):

  if n <= 1:

      return n

  else:

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

n=int(input('Enter n…'))

x=fib(n)

print (n,"th Fibonacci number is...",x)

output:

Enter n…5

5 th Fibonacci number is... 5

3.Program to find sum of the digits of a number

def sumd(n):
    if n == 0:
        return 0
    else:
        return n%10 + sumd(n//10)
n=int(input('Enter n'))
s=sumd(n)
print ("sum of the digits of ..",n ," ..is.. ",s)

output:

Enter n...123

sum of the digits of .. 123  ..is..  6

4.Program to convert decimal number to binary using recursion

def decb(n):
    if n==0:
        return 0
    else:
        return n%2 + 10* decb(n//2)
n=int(input('Enter n.:'))
b=decb(n)
print("The binary equivalent of ..",n ," ..is.. ",b)

output

Enter n.:12

The binary equivalent of .. 12  ..is..  1100

5.Program to find sum of n natural numbers using recursion

def sum(n):
    if n ==0:
        return 0
    else:
        return n + sum(n-1)

n=int(input('Enter n..'))
s=sum(n)
print("The sum of natural numbers up to ...",n ," ..is.. ",s)

output

Enter n..10

The sum of natural numbers up to ... 10  ..is..  55

6.Program to find nPr using a recursive factorial function

def fact(n):
  if n==0:
    return 1
 else:
    return n*fact(n-1)
n=int(input('Enter n..'))
r=int(input('Enter r..'))
print("nPr=", fact(n)//fact(n-r))

output

Enter n..5

Enter r..3

nPr= 60

7.GCD of two numbers using recursion ( university question)

def gcd_recursive(a, b):

    if b == 0:

        return a

    else:

        return gcd_recursive(b, a % b)

x=int(input('Enter x='))

y=int(input('Enter y='))

gcd=gcd_recursive(x,y)

print(f'gcd of {x} and {y} is={gcd}')

Note: a*b= gcd(a,b)*lcm(a,b) . So we can find lcm(a,b) after finding gcd(a,b).

8.Recursive Function to add two positive numbers.

def add_positive_numbers(a, b):
# Base case: if one of the numbers is zero
    if b == 0:
        return a
# Recursive case: increment a and decrement b
    return add_positive_numbers(a + 1, b - 1)

# Input two positive numbers
num1 = int(input("Enter the first positive number: "))
num2 = int(input("Enter the second positive number: "))


# Ensure both numbers are positive
if num1 < 0 or num2 < 0:
    print("Both numbers must be positive.")
else:
# Calculate the sum using recursion
    result = add_positive_numbers(num1, num2)
# Print the result
print(f"The sum of {num1} and {num2} is {result}")

9.Recursive function to multiply two positive numbers.
# Recursive function to multiply two numbers
def multiply(a, b):
# Base case: if one of the numbers is zero
    if b == 0:
        return 0
# Recursive case: multiply by adding a to the result of multiplying a with (b - 1)
    return a + multiply(a, b - 1)

# Input two numbers
num1 = int(input("Enter the first number: "))
num2 = int(input("Enter the second number: "))

# Calculate the product using recursion
result = multiply(num1, num2)

# Print the result
print(f"The product of {num1} and {num2} is {result}")

10.You are given two positive integers, a and b. Write a Python program using recursion to find the Least Common Multiple (LCM) of these integers. You are not allowed to directly calculate the LCM formula, but must instead use the relationship between GCD and LCM.(university question)

def gcd_recursive(a, b):

    if b == 0:

        return a

    else:

        return gcd_recursive(b, a % b)

# Input

x = int(input("Enter x = "))

y = int(input("Enter y = "))

# Compute GCD

gcd = gcd_recursive(x, y)

# Compute LCM using formula

lcm = (x * y) // gcd

# Output

print(f"GCD of {x} and {y} is = {gcd}")

print(f"LCM of {x} and {y} is = {lcm}")

11.Write a recursive function to find an array's minimum and maximum elements. Your method should return a tuple (a, b), where a is the minimum element and b is the maximum. ( university question)

def find_min_max(arr, n):

    # Base case: only one element

    if n == 1:

        return arr[0], arr[0]

    # Recursive call on remaining elements

    min_val, max_val = find_min_max(arr, n - 1)

    # Compare last element with current min and max

    if arr[n - 1] < min_val:

        min_val = arr[n - 1]

    if arr[n - 1] > max_val:

        max_val = arr[n - 1]

    return min_val, max_val

# Input

arr = list(map(int, input("Enter array elements: ").split()))

n = len(arr)

# Function call

minimum, maximum = find_min_max(arr, n)

print("Minimum element =", minimum)

print("Maximum element =", maximum)

# Output

Enter array elements: 3 5 1 9 2

Minimum element = 1

Maximum element = 9