The Art of Recursion

What is Recursion? 🤔

Recursion is a powerful programming technique where a function calls itself to solve a problem. Think of it like a set of Russian nesting dolls; each doll contains a smaller, identical version of itself, until you get to the final, smallest doll that can't be opened.

Every recursive solution has two essential parts:

The Base Case: This is the "smallest doll." It's the simplest version of the problem that can be solved directly, without making another recursive call. The base case acts as the stopping condition. Without it, you get infinite recursion and a stack overflow error!
The Recursive Step: This is where the magic happens. The function breaks the current problem down into a slightly smaller version of itself and calls itself to solve that smaller piece. It then combines the result of that call to solve the original problem.

Why Use It?

While anything you can do with recursion you can also do with loops (iteration), recursion is preferred when it leads to a simpler, more elegant solution. It shines when working with data structures that are themselves defined recursively, like trees and linked lists. It's also the cornerstone of the functional programming paradigm.

Factorial Examples Across Languages

The factorial function is the "Hello, World!" of recursion. Let's see how it's implemented in a few different languages you're studying in CSE 240 and beyond. The goal is to calculate n!.

C++

#include <iostream>

// The classic recursive implementation in C++
int factorial(int n) {
    // Base Case: 0! is 1
    if (n == 0) {
        return 1;
    }
    // Recursive Step: n * (n-1)!
    else {
        return n * factorial(n - 1);
    }
}

int main() {
    std::cout << "5! is " << factorial(5) << std::endl; // Output: 120
    return 0;
}

Scheme

In Scheme, recursion is the primary way to perform iteration.

; define the factorial procedure
(define (factorial n)
  ; Base Case: if n is 0, the result is 1
  (if (= n 0)
      1
      ; Recursive Step: n * (factorial of n-1)
      (* n (factorial (- n 1)))))

; call the procedure
(display (factorial 5)) ; Output: 120
(newline)

Prolog

In Prolog, recursion is expressed as rules that refer to themselves.

% Base Case: The factorial of 0 is 1.
factorial(0, 1).

% Recursive Step: The factorial of N is F if...
factorial(N, F) :-
    N > 0,
    N1 is N - 1,         % Calculate N-1
    factorial(N1, F1),   % Recursively find the factorial of N-1
    F is N * F1.         % F is N times the result.

% Query:
% ?- factorial(5, Result).
% Result = 120.

Python

def factorial(n):
    # Base Case
    if n == 0:
        return 1
    # Recursive Step
    else:
        return n * factorial(n - 1)

print(f"5! is {factorial(5)}") # Output: 120

Java

public class RecursionExample {

    public static int factorial(int n) {
        // Base Case
        if (n == 0) {
            return 1;
        }
        // Recursive Step
        else {
            return n * factorial(n - 1);
        }
    }

    public static void main(String[] args) {
        System.out.println("5! is " + factorial(5)); // Output: 120
    }
}

Go

package main

import "fmt"

func factorial(n int) int {
    // Base Case
    if n == 0 {
        return 1
    }
    // Recursive Step
    return n * factorial(n-1)
}

func main() {
    fmt.Printf("5! is %d\n", factorial(5)) // Output: 120
}

Rust

fn factorial(n: u64) -> u64 {
    // Base Case
    if n == 0 {
        1
    } 
    // Recursive Step (no explicit return needed for the last expression)
    else {
        n * factorial(n - 1)
    }
}

fn main() {
    println!("5! is {}", factorial(5)); // Output: 120
}