Recursion is a powerful technique where a function calls itself to solve smaller instances of a problem. Today, we'll explore three classic recursive problems, breaking each down step-by-step to build your confidence in using recursion effectively.

Problem One: Sum from n to 1

Task: Create a function get_sum(n) that returns the sum of all integers from n to 1.

Example:
get_sum(5) ➝ 15 (because 5 + 4 + 3 + 2 + 1 = 15)
get_sum(1) ➝ 1

Breakdown:

  • Base case: If n == 1, return 1.
  • Recursive step: Return n + get_sum(n - 1) until n reaches 1. 
def get_sum(n):
    if n == 1:
        return 1
    else:
        return n + get_sum(n - 1)

Problem Two: Countdown List using Recursion

Task: Write a recursive function solution(n) that returns a list of integers from n down to 1.

Example:
solution(5) ➝ [5, 4, 3, 2, 1]

🧠 Breakdown:

  • Base case: If n == 0, return an empty list.
  • Recursive step: Return [n] + solution(n - 1) 
def solution(n):
    if n == 0:
        return []
    else:
        return [n] + solution(n - 1)

Problem Three: Sum of Digits Raised to Their Position

Task: Given a positive integer n, return the sum of each digit raised to the power of its position (starting from the right, 1-indexed). Use recursion.

Example:
solution(123) ➝ 3¹ + 2² + 1³ = 3 + 4 + 1 = 8

Breakdown:

  • Base case: If n == 0, return 0.

  • Step:

    • Extract the last digit using n % 10.
    • Remove the digit using n // 10.
    • Add (last_digit ** position) to the recursive result. 
def solution(n, pos=1):
    if n == 0:
        return 0

    last_digit = n % 10
    n //= 10

    return (last_digit ** pos) + solution(n, pos + 1)

Conclusion

Each of these examples shows how recursion breaks down complex problems into simpler sub-problems.