Recursion

🔄 What is Recursion?

Recursion is when a function calls itself. It's a powerful technique for solving problems that can be broken down into smaller, similar sub-problems.

Anatomy of Recursion

Every recursive function needs two parts:

1. Base Case

The condition that stops the recursion - the "smallest doll"

2. Recursive Case

The function calling itself with a simpler problem

Function RecursiveFunction(n)
    If n == baseCondition Then
        Return baseResult  # BASE CASE - stops recursion
    Else
        Return RecursiveFunction(n - 1)  # RECURSIVE CASE
    Endif
Endfunction

🔢 Classic Example: Factorial

Factorial: n! = n × (n-1) × (n-2) × ... × 1

Algorithm RecursiveFactorial

Function Factorial(n)
    # BASE CASE: 0! = 1 and 1! = 1
    If n <= 1 Then
        Return 1
    Else
        # RECURSIVE CASE: n! = n × (n-1)!
        Return n * Factorial(n - 1)
    Endif
Endfunction

# Test the function
Print "5! =", Factorial(5)
Print "7! =", Factorial(7)

Endalgorithm

How Factorial(5) Works:

Factorial(5)
  = 5 * Factorial(4)
  = 5 * (4 * Factorial(3))
  = 5 * (4 * (3 * Factorial(2)))
  = 5 * (4 * (3 * (2 * Factorial(1))))
  = 5 * (4 * (3 * (2 * 1)))  # Base case reached!
  = 5 * (4 * (3 * 2))
  = 5 * (4 * 6)
  = 5 * 24
  = 120

🔢 Fibonacci with Recursion

Algorithm RecursiveFibonacci

Function Fibonacci(n)
    # BASE CASES
    If n == 0 Then
        Return 0
    Else If n == 1 Then
        Return 1
    Else
        # RECURSIVE CASE: fib(n) = fib(n-1) + fib(n-2)
        Return Fibonacci(n - 1) + Fibonacci(n - 2)
    Endif
Endfunction

Print "First 10 Fibonacci numbers:"
For i = 0 To 9
    Print "F(", i, ") =", Fibonacci(i)
Endfor

Endalgorithm

More Recursive Examples

Sum of Numbers

Algorithm RecursiveSum

Function SumToN(n)
    # BASE CASE: sum of 0 is 0
    If n == 0 Then
        Return 0
    Else
        # RECURSIVE: sum(n) = n + sum(n-1)
        Return n + SumToN(n - 1)
    Endif
Endfunction

Print "Sum 1 to 10:", SumToN(10)
Print "Sum 1 to 100:", SumToN(100)

Endalgorithm

Power Function

Algorithm RecursivePower

Function Power(base, exponent)
    # BASE CASE: anything to power 0 is 1
    If exponent == 0 Then
        Return 1
    Else
        # RECURSIVE: base^exp = base × base^(exp-1)
        Return base * Power(base, exponent - 1)
    Endif
Endfunction

Print "2^5 =", Power(2, 5)
Print "3^4 =", Power(3, 4)
Print "10^3 =", Power(10, 3)

Endalgorithm

🆚 Recursion vs. Iteration

You can solve the same problem with loops or recursion:

Factorial with Loop

Function FactorialIterative(n)
    var result = 1
    For i = 1 To n
        result = result * i
    Endfor
    Return result
Endfunction

Factorial with Recursion

Function FactorialRecursive(n)
    If n <= 1 Then
        Return 1
    Else
        Return n * FactorialRecursive(n - 1)
    Endif
Endfunction

More Recursive Examples

Countdown

Algorithm RecursiveCountdown

Procedure Countdown(n)
    # BASE CASE
    If n == 0 Then
        Print "Blast off! 🚀"
    Else
        # RECURSIVE CASE
        Print n
        Countdown(n - 1)
    Endif
Endprocedure

Countdown(10)

Endalgorithm

Sum of Array

Algorithm RecursiveArraySum

Function SumArray(arr, index, size)
    # BASE CASE: reached end of array
    If index >= size Then
        Return 0
    Else
        # RECURSIVE: current element + sum of rest
        Return arr[index] + SumArray(arr, index + 1, size)
    Endif
Endfunction

var numbers = [10, 20, 30, 40, 50]
var total = SumArray(numbers, 0, 5)

Print "Sum of array:", total

Endalgorithm

Recursion Pitfalls

Function BadRecursion(n)
    Return n + BadRecursion(n - 1)
    # No base case! Will crash!
Endfunction

Function GoodRecursion(n)
    If n == 0 Then
        Return 0  # Base case!
    Else
        Return n + GoodRecursion(n - 1)
    Endif
Endfunction

Key Takeaways

• ✅ Recursion is when a function calls itself
• ✅ Must have a base case to stop recursion
• ✅ Must have a recursive case that moves toward base case
• ✅ Each recursive call works on a simpler problem
• ✅ Great for problems that break into similar sub-problems
• ✅ Can be more elegant than loops for certain problems
• ✅ Watch out for infinite recursion and stack overflow

💪 Practice Exercises