Recursion Examples

For each problem, try to solve it on your own first. When you're ready to see the solution, click on the dropdown to reveal it.

1. Sum of numbers from 1 to n

Write a recursive function to calculate the sum of all numbers from 1 to n.

Click to see solution 
def sum_to_n(n):
    if n == 1:
        return 1
    else:
        return n + sum_to_n(n - 1)

2. Product of numbers from 1 to n (factorial)

Implement a recursive function to compute the product of all numbers from 1 to n (essentially, the factorial of n).

Click to see solution 
def factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n - 1)

3. Print numbers from n to 1

Create a recursive function to print all numbers from n to 1 (backwards).

Click to see solution 
def print_backward(n):
    if n == 0:
        return
    else:
        print(n)
        print_backward(n - 1)

4. Calculate nth power

Develop a recursive function to calculate the nth power of a given number.

Click to see solution 
def power(base, exponent):
    if exponent == 0:
        return 1
    else:
        return base * power(base, exponent - 1)

5. Check if string is palindrome

Write a recursive function to determine if a given string is a palindrome.

Click to see solution 
def is_palindrome(s):
    if len(s) <= 1:
        return True
    else:
        return s[0] == s[-1] and is_palindrome(s[1:-1])

Implement a recursive binary search algorithm.

Click to see solution 
def binary_search(arr, target, low, high):
    if low > high:
        return -1
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return binary_search(arr, target, low, mid - 1)
    else:
        return binary_search(arr, target, mid + 1, high)

7. Greatest Common Divisor (GCD)

Create a recursive function to find the greatest common divisor (GCD) of two numbers using the Euclidean algorithm.

Click to see solution 
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

8. Fibonacci sequence

Develop a recursive function to generate the nth term of the Fibonacci sequence.

Click to see solution 
def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

9. Count occurrences of a digit

Write a recursive function to count the number of occurrences of a specific digit in a given number.

Click to see solution 
def count_digit(number, digit):
    if number == 0:
        return 0
    if number % 10 == digit:
        return 1 + count_digit(number // 10, digit)
    return count_digit(number // 10, digit)

10. Reverse a string

Implement a recursive function to reverse a given string.

Click to see solution 
def reverse_string(s):
    if len(s) <= 1:
        return s
    else:
        return reverse_string(s[1:]) + s[0]

11. Sum of digits

Create a recursive function to find the sum of digits of a given number.

Click to see solution 
def sum_of_digits(n):
    if n < 10:
        return n
    else:
        return n % 10 + sum_of_digits(n // 10)

12. Check if array is sorted

Develop a recursive function to check if a given array is sorted in ascending order.

Click to see solution 
def is_sorted(arr):
    if len(arr) <= 1:
        return True
    return arr[0] <= arr[1] and is_sorted(arr[1:])

13. Calculate string length

Write a recursive function to calculate the length of a string without using any built-in functions.

Click to see solution 
def string_length(s):
    if s == "":
        return 0
    else:
        return 1 + string_length(s[1:])

14. Find minimum element in array

Implement a recursive function to find the minimum element in an array.

Click to see solution 
def find_min(arr):
    if len(arr) == 1:
        return arr[0]
    else:
        return min(arr[0], find_min(arr[1:]))

15. Generate string permutations

Create a recursive function to generate all possible permutations of a string.

Click to see solution 
def permutations(s):
    if len(s) <= 1:
        return [s]
    else:
        perms = []
        for i, char in enumerate(s):
            for perm in permutations(s[:i] + s[i+1:]):
                perms.append(char + perm)
        return perms

16. Convert decimal to binary

Develop a recursive function to convert a decimal number to its binary representation.

Click to see solution 
def decimal_to_binary(n):
    if n == 0:
        return "0"
    elif n == 1:
        return "1"
    else:
        return decimal_to_binary(n // 2) + str(n % 2)

17. Tower of Hanoi

Write a recursive function to solve the Tower of Hanoi problem.

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

18. Flatten a nested list

Implement a recursive function to flatten a nested list.

Click to see solution 
def flatten_list(nested_list):
    if not nested_list:
        return []
    if isinstance(nested_list[0], list):
        return flatten_list(nested_list[0]) + flatten_list(nested_list[1:])
    return [nested_list[0]] + flatten_list(nested_list[1:])

19. Sum of elements in a linked list

Create a recursive function to calculate the sum of elements in a linked list.

Click to see solution 
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def sum_linked_list(head):
    if not head:
        return 0
    return head.val + sum_linked_list(head.next)

20. Check if a number is prime

Develop a recursive function to determine if a number is prime.

Click to see solution 
def is_prime(n, divisor=2):
    if n <= 2:
        return n == 2
    if n % divisor == 0:
        return False
    if divisor * divisor > n:
        return True
    return is_prime(n, divisor + 1)