4.6 - Recursion

Recursion is a powerful programming technique where a method calls itself to solve a problem. It's particularly useful for tasks that can be broken down into smaller, similar subproblems. While recursion can sometimes be challenging to understand at first, mastering it adds a valuable tool to your programming toolkit.

What is Recursion?

Recursion occurs when a method calls itself directly or indirectly. Each recursive call works on a smaller version of the original problem, bringing the overall solution closer to completion.

A recursive method typically has two parts:

1. Base case(s): Condition(s) that stop the recursion
2. Recursive step: The part where the method calls itself with a modified input

The Anatomy of a Recursive Method

Here's a simple example of a recursive method that counts down from a given number:

void CountDown(int n)
{
    // Base case
    if (n <= 0)
    {
        Console.WriteLine("Blastoff!");
        return;
    }
    
    // Current step
    Console.WriteLine(n);
    
    // Recursive step
    CountDown(n - 1);
}

If we call CountDown(3), the execution would be:

1. Print 3
2. Call CountDown(2)
   • Print 2
   • Call CountDown(1)
     • Print 1
     • Call CountDown(0)
       • Print Blastoff!
       • Return to CountDown(1)
     • Return to CountDown(2)
   • Return to CountDown(3)

• Return to the original caller

A Simpler Example: Sum of Numbers

Before diving into classic recursion examples, let's look at a very simple example that might be easier to understand. Let's write a recursive method to calculate the sum of numbers from 1 to n:

int SumNumbers(int n)
{
    // Base case
    if (n <= 0)
    {
        return 0;
    }
    
    // Recursive step
    return n + SumNumbers(n - 1);
}

If we call SumNumbers(5), here's what happens:

• SumNumbers(5) = 5 + SumNumbers(4)
  • SumNumbers(4) = 4 + SumNumbers(3)
    • SumNumbers(3) = 3 + SumNumbers(2)
      • SumNumbers(2) = 2 + SumNumbers(1)
        • SumNumbers(1) = 1 + SumNumbers(0)
          • SumNumbers(0) = 0 (base case)
        • Returns 1 + 0 = 1
      • Returns 2 + 1 = 3
    • Returns 3 + 3 = 6
  • Returns 4 + 6 = 10
• Returns 5 + 10 = 15

This example shows how recursion breaks down a problem (summing numbers) into smaller versions of the same problem (summing fewer numbers).

Classic Recursion Examples

1. Factorial Calculation

The factorial of a non-negative integer n (written as n!) is the product of all positive integers less than or equal to n.

For example: 5! = 5 × 4 × 3 × 2 × 1 = 120

Here's how to calculate factorial recursively:

int Factorial(int n)
{
    // Base case
    if (n <= 1)
    {
        return 1;
    }
    
    // Recursive step
    return n * Factorial(n - 1);
}

Tracing Factorial(4):

• Factorial(4) = 4 * Factorial(3)
  • Factorial(3) = 3 * Factorial(2)
    • Factorial(2) = 2 * Factorial(1)
      • Factorial(1) = 1 (base case)
    • Returns 2 * 1 = 2
  • Returns 3 * 2 = 6
• Returns 4 * 6 = 24

2. Fibonacci Sequence

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1.

For example: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Here's a recursive implementation:

int Fibonacci(int n)
{
    // Base cases
    if (n <= 0)
        return 0;
    if (n == 1)
        return 1;
    
    // Recursive step
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Tracing Fibonacci(4):

• Fibonacci(4) = Fibonacci(3) + Fibonacci(2)
  • Fibonacci(3) = Fibonacci(2) + Fibonacci(1)
    • Fibonacci(2) = Fibonacci(1) + Fibonacci(0)
      • Fibonacci(1) = 1 (base case)
      • Fibonacci(0) = 0 (base case)
    • Returns 1 + 0 = 1
    • Fibonacci(1) = 1 (base case)
  • Returns 1 + 1 = 2
  • Fibonacci(2) = Fibonacci(1) + Fibonacci(0)
    • Fibonacci(1) = 1 (base case)
    • Fibonacci(0) = 0 (base case)
  • Returns 1 + 0 = 1
• Returns 2 + 1 = 3

Recursion vs. Iteration

Many problems can be solved using either recursion or iteration (loops). Each approach has its advantages:

Recursion Advantages:

• Often leads to cleaner, more elegant code for certain problems
• Naturally models problems that have a recursive structure
• Can be easier to understand for inherently recursive problems

Iteration Advantages:

• Generally more efficient (no function call overhead)
• Doesn't risk stack overflow for large inputs
• Often easier to trace through execution

Example: Sum of Array Elements

Recursive approach:

int SumArray(int[] array, int index)
{
    // Base case
    if (index >= array.Length)
        return 0;
    
    // Recursive step
    return array[index] + SumArray(array, index + 1);
}

// Usage
int[] numbers = { 1, 2, 3, 4, 5 };
int sum = SumArray(numbers, 0); // Returns 15

Iterative approach:

int SumArray(int[] array)
{
    int sum = 0;
    for (int i = 0; i < array.Length; i++)
    {
        sum += array[i];
    }
    return sum;
}

// Usage
int[] numbers = { 1, 2, 3, 4, 5 };
int sum = SumArray(numbers); // Returns 15

Potential Pitfalls of Recursion

1. Stack Overflow

Each recursive call adds a new frame to the call stack. If recursion goes too deep, it can cause a stack overflow exception:

void InfiniteRecursion()
{
    InfiniteRecursion(); // No base case! Will cause stack overflow
}

2. Inefficient Computation

Simple recursive implementations can lead to redundant calculations. For example, the naive Fibonacci implementation recalculates the same values multiple times:

// Inefficient - many redundant calculations
int Fibonacci(int n)
{
    if (n <= 0) return 0;
    if (n == 1) return 1;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

For Fibonacci(5), Fibonacci(3) is calculated twice, and Fibonacci(2) is calculated three times!

3. Solutions to Recursion Pitfalls

Tail Recursion

A tail-recursive function is one where the recursive call is the last operation in the function:

int FactorialTail(int n, int accumulator = 1)
{
    if (n <= 1)
        return accumulator;
    
    return FactorialTail(n - 1, n * accumulator);
}

Memoization

Memoization stores previously calculated results to avoid redundant calculations:

Dictionary<int, int> fibCache = new Dictionary<int, int>();

int FibonacciMemoized(int n)
{
    if (n <= 0) return 0;
    if (n == 1) return 1;
    
    // Check if we've already calculated this value
    if (fibCache.ContainsKey(n))
        return fibCache[n];
    
    // Calculate and store the result
    int result = FibonacciMemoized(n - 1) + FibonacciMemoized(n - 2);
    fibCache[n] = result;
    
    return result;
}

Recursion in Game Development

Recursion can be particularly useful in game development for problems with a hierarchical or nested structure.

1. Tree Traversal

Game objects often form a hierarchy (parent-child relationships). Recursion is perfect for traversing these structures:

using UnityEngine;

public class HierarchyTraversal : MonoBehaviour
{
    public void PrintHierarchy(Transform root, int depth = 0)
    {
        // Print the current object with indentation based on depth
        string indent = new string('-', depth * 2);
        Debug.Log($"{indent}{root.name}");
        
        // Recursively process all children
        foreach (Transform child in root)
        {
            PrintHierarchy(child, depth + 1);
        }
    }
    
    void Start()
    {
        // Print the entire hierarchy starting from this GameObject
        PrintHierarchy(transform);
    }
}

2. Procedural Generation

Recursion is excellent for generating fractal-like structures or procedural content:

using UnityEngine;

public class FractalTree : MonoBehaviour
{
    public GameObject branchPrefab;
    public int maxDepth = 5;
    public float branchLength = 1f;
    public float branchAngle = 30f;
    public float scaleFactor = 0.8f;
    
    void Start()
    {
        GenerateBranch(transform.position, Vector3.up, branchLength, 0);
    }
    
    void GenerateBranch(Vector3 startPos, Vector3 direction, float length, int depth)
    {
        // Base case
        if (depth >= maxDepth)
            return;
        
        // Create the current branch
        Vector3 endPos = startPos + direction * length;
        GameObject branch = Instantiate(branchPrefab, transform);
        
        // Position and scale the branch
        branch.transform.position = startPos;
        branch.transform.up = direction;
        branch.transform.localScale = new Vector3(0.1f, length, 0.1f);
        
        // Recursive step - create left and right branches
        Quaternion leftRotation = Quaternion.AngleAxis(-branchAngle, Vector3.forward);
        Quaternion rightRotation = Quaternion.AngleAxis(branchAngle, Vector3.forward);
        
        Vector3 leftDir = leftRotation * direction;
        Vector3 rightDir = rightRotation * direction;
        
        float newLength = length * scaleFactor;
        
        GenerateBranch(endPos, leftDir, newLength, depth + 1);
        GenerateBranch(endPos, rightDir, newLength, depth + 1);
    }
}

3. Pathfinding in a Maze

Recursion can be used for maze generation and solving:

using UnityEngine;
using System.Collections.Generic;

public class MazeSolver : MonoBehaviour
{
    // 0 = path, 1 = wall
    private int[,] maze = {
        {0, 1, 0, 0, 0},
        {0, 1, 0, 1, 0},
        {0, 0, 0, 1, 0},
        {1, 1, 0, 1, 0},
        {0, 0, 0, 0, 0}
    };
    
    private bool[,] visited;
    private List<Vector2Int> path = new List<Vector2Int>();
    
    void Start()
    {
        visited = new bool[maze.GetLength(0), maze.GetLength(1)];
        
        // Try to find a path from (0,0) to (4,4)
        if (FindPath(0, 0, 4, 4))
        {
            Debug.Log("Path found!");
            foreach (Vector2Int pos in path)
            {
                Debug.Log($"({pos.x}, {pos.y})");
            }
        }
        else
        {
            Debug.Log("No path found!");
        }
    }
    
    bool FindPath(int x, int y, int targetX, int targetY)
    {
        // Check if position is valid
        if (x < 0 || y < 0 || x >= maze.GetLength(0) || y >= maze.GetLength(1))
            return false;
        
        // Check if this is a wall or already visited
        if (maze[x, y] == 1 || visited[x, y])
            return false;
        
        // Mark as visited and add to path
        visited[x, y] = true;
        path.Add(new Vector2Int(x, y));
        
        // Check if we reached the target
        if (x == targetX && y == targetY)
            return true;
        
        // Try all four directions (recursive step)
        if (FindPath(x + 1, y, targetX, targetY) || // Right
            FindPath(x - 1, y, targetX, targetY) || // Left
            FindPath(x, y + 1, targetX, targetY) || // Down
            FindPath(x, y - 1, targetX, targetY))   // Up
        {
            return true;
        }
        
        // If no path found, backtrack
        path.RemoveAt(path.Count - 1);
        return false;
    }
}

When to Use Recursion in Unity

Recursion can be powerful, but use it judiciously in Unity:

Good Use Cases:

• Traversing hierarchical structures (transform hierarchies, quadtrees, etc.)
• Procedural generation with self-similar patterns
• Parsing complex data structures
• Implementing divide-and-conquer algorithms

Caution Areas:

• Update/FixedUpdate methods: Never use recursion in these frequently called methods as they run every frame and could quickly cause stack overflow
• Large data sets: Be careful with deep recursion that might cause stack overflow
• Performance-critical code: Consider iterative alternatives for better performance
• Mobile platforms: Mobile devices often have more limited stack space, making them more vulnerable to stack overflow errors

Unity Performance Warning

In Unity, you should be extremely cautious about using recursion in any code that runs frequently, such as:

1. MonoBehaviour lifecycle methods: Update(), FixedUpdate(), LateUpdate(), etc.
2. Rendering callbacks: OnRenderImage(), OnPostRender(), etc.
3. Physics callbacks: OnCollisionEnter(), OnTriggerStay(), etc.
4. Input handling: Methods called every frame to process input

Instead, use recursion primarily in:

• Editor scripts
• One-time initialization code
• Procedural generation that happens before gameplay
• Utility functions that process data structures with known, limited depth

When in doubt, consider using an iterative approach with explicit stacks or queues for better performance and safety.

Best Practices for Recursion

1. Always have a valid base case to prevent infinite recursion
2. Ensure progress toward the base case with each recursive call
3. Consider the stack depth for large inputs
4. Use memoization for problems with overlapping subproblems
5. Test with edge cases (empty inputs, minimum/maximum values)
6. Consider iterative alternatives for performance-critical code

Summary

• Recursion is a technique where a method calls itself to solve a problem
• Every recursive solution needs at least one base case to stop the recursion
• Recursive solutions can be elegant but may have performance implications
• Common recursive patterns include tree traversal, divide-and-conquer, and backtracking
• In Unity, recursion is useful for hierarchical structures and procedural generation
• Always be mindful of stack depth and consider memoization for efficiency

Recursion is like a powerful tool that, when used appropriately, can lead to elegant solutions for complex problems. As you practice, you'll develop an intuition for when recursion is the right approach and how to implement it effectively in your Unity projects.