Recursion Programs

Introduction

In the previous chapter, you learned the theory behind recursion—base cases, recursive cases, and the call stack. Now it is time to apply that knowledge to solve real programming problems.

This chapter presents several classic recursive programs with complete code, output, and step-by-step explanations. Each program demonstrates a different aspect of recursion and helps you build problem-solving skills for university and competitive exams.

Program 1 — Factorial

Problem: Find the factorial of a given number using recursion.

Logic: n! = n × (n-1)! and 0! = 1.

def factorial(n):
    if n == 0 or n == 1:
        return 1
    return n * factorial(n - 1)

num = int(input("Enter a number: "))
print(f"Factorial of {num} = {factorial(num)}")

Output:
Enter a number: 5
Factorial of 5 = 120

Trace:
factorial(5) → 5 × factorial(4)
  factorial(4) → 4 × factorial(3)
    factorial(3) → 3 × factorial(2)
      factorial(2) → 2 × factorial(1)
        factorial(1) → 1  (base case)
      = 2 × 1 = 2
    = 3 × 2 = 6
  = 4 × 6 = 24
= 5 × 24 = 120

Program 2 — Fibonacci Series

Problem: Find the nth Fibonacci number using recursion.

Logic: F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2).

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

for i in range(10):
    print(fibonacci(i), end=" ")
print()

Output:
0 1 1 2 3 5 8 13 21 34

Program 3 — Power of a Number

Problem: Compute base^exp using recursion.

def power(base, exp):
    if exp == 0:
        return 1
    return base * power(base, exp - 1)

print(power(2, 10))
print(power(5, 3))
print(power(7, 0))

Output:
1024
125
1

Program 4 — Sum of Digits

Problem: Find the sum of all digits of a number recursively.

Logic: sum(n) = n % 10 + sum(n // 10).

def sum_of_digits(n):
    n = abs(n)
    if n < 10:
        return n
    return (n % 10) + sum_of_digits(n // 10)

print(sum_of_digits(12345))
print(sum_of_digits(999))
print(sum_of_digits(5))

Output:
15
27
5

Trace for sum_of_digits(1234):
1234 → 4 + sum_of_digits(123)
  123 → 3 + sum_of_digits(12)
    12 → 2 + sum_of_digits(1)
      1 → 1  (base case)
    = 2 + 1 = 3
  = 3 + 3 = 6
= 4 + 6 = 10

Program 5 — Reverse a String

Problem: Reverse a string using recursion.

Logic: reverse(s) = reverse(s[1:]) + s[0].

def reverse_string(s):
    if len(s) <= 1:
        return s
    return reverse_string(s[1:]) + s[0]

print(reverse_string("Hello"))
print(reverse_string("Python"))
print(reverse_string("A"))

Output:
olleH
nohtyP
A

Program 6 — Palindrome Check

Problem: Check if a string is a palindrome using recursion.

def is_palindrome(s):
    if len(s) <= 1:
        return True
    if s[0] != s[-1]:
        return False
    return is_palindrome(s[1:-1])

print(is_palindrome("racecar"))
print(is_palindrome("hello"))
print(is_palindrome("madam"))
print(is_palindrome("abba"))

Output:
True
False
True
True

Trace for is_palindrome("racecar"):
racecar → r == r → is_palindrome("aceca")
  aceca → a == a → is_palindrome("cec")
    cec → c == c → is_palindrome("e")
      "e" → length 1 → True (base case)

Program 7 — Tower of Hanoi

Problem: Move n disks from source to destination using an auxiliary peg.

Logic: Move n-1 disks to auxiliary, move the largest disk to destination, then move n-1 disks from auxiliary to destination.

def tower_of_hanoi(n, source, destination, auxiliary):
    if n == 1:
        print(f"Move disk 1 from {source} to {destination}")
        return
    tower_of_hanoi(n - 1, source, auxiliary, destination)
    print(f"Move disk {n} from {source} to {destination}")
    tower_of_hanoi(n - 1, auxiliary, destination, source)

tower_of_hanoi(3, "A", "C", "B")

Output:
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

Key Takeaways

Every recursive program must have a base case.

The recursive case must make progress toward the base case.

Factorial, Fibonacci, and power are classic recursion examples.

String problems (reverse, palindrome) use slicing with recursion.

Tower of Hanoi is a classic divide-and-conquer recursion problem.

Tracing recursion step by step helps in understanding and debugging.

University Exam Tip

University exams often ask you to trace the recursive calls for a given input. Always draw the call stack or write the step-by-step trace to earn full marks. The Tower of Hanoi and Fibonacci are among the most frequently asked recursion programs.

Practice Questions

Q1. Write a recursive function to find the GCD (Greatest Common Divisor) of two numbers.

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

print(gcd(12, 8))   # 4
print(gcd(100, 75))  # 25

Q2. Write a recursive function to find the length of a string without using len().

def str_length(s):
    if s == "":
        return 0
    return 1 + str_length(s[1:])

print(str_length("Hello"))   # 5
print(str_length(""))        # 0

Q3. What is the output of fibonacci(6)? Trace it.

fibonacci(6)
= fibonacci(5) + fibonacci(4)
= (fibonacci(4)+fibonacci(3)) + (fibonacci(3)+fibonacci(2))
= ((fibonacci(3)+fibonacci(2)) + (fibonacci(2)+fibonacci(1))) + ...
= 8

Q4. How many moves are required for Tower of Hanoi with n disks?

Answer: 2ⁿ - 1 moves. For 3 disks: 7 moves. For 4 disks: 15 moves.

Q5. Write a recursive function to find the maximum element in a list.

def find_max(lst, n=None):
    if n is None:
        n = len(lst)
    if n == 1:
        return lst[0]
    return max(lst[n-1], find_max(lst, n-1))

print(find_max([3, 7, 2, 9, 4]))  # 9