PHP Recursion Alternatives Guide

php-recursion-alternative-guide.md

PHP Recursion Alternatives Guide

This guide demonstrates how to convert common recursive patterns into iterative solutions in PHP, with a focus on functional programming principles and code safety.

Directory Scanner

Converting a recursive directory scanner to an iterative approach using a queue:

<?php
declare(strict_types=1);

function scanDirectoryIterative(string $path): array 
{
    $files = [];
    $queue = new SplQueue();
    $queue->enqueue($path);
    
    while (!$queue->isEmpty()) {
        $currentPath = $queue->dequeue();
        $entries = scandir($currentPath);
        
        foreach ($entries as $entry) {
            if ($entry === '.' || $entry === '..') {
                continue;
            }
            
            $fullPath = $currentPath . DIRECTORY_SEPARATOR . $entry;
            if (is_dir($fullPath)) {
                $queue->enqueue($fullPath);
            } else {
                $files[] = $fullPath;
            }
        }
    }
    
    return $files;
}

Key Features:

• Uses SplQueue for FIFO processing
• Single return point
• Explicit type declarations
• No recursion or deep nesting
• Pure function with no side effects

Factorial Calculator

Converting a recursive factorial function to an iterative approach:

<?php
declare(strict_types=1);

function factorialIterative(int $n): int 
{
    if ($n < 0) {
        throw new InvalidArgumentException('Factorial not defined for negative numbers');
    }
    
    $result = 1;
    for ($i = 2; $i <= $n; $i++) {
        $result *= $i;
    }
    
    return $result;
}

Key Features:

• Input validation with typed exception
• Single loop implementation
• Explicit type declarations
• Guard clause for invalid input
• Pure function with predictable output

Tree Traversal

Converting a recursive tree traversal to an iterative approach using a stack:

<?php
declare(strict_types=1);

class TreeNode {
    public function __construct(
        public readonly mixed $value,
        public readonly ?TreeNode $left = null,
        public readonly ?TreeNode $right = null
    ) {}
}

function traverseTreeIterative(TreeNode $root): array 
{
    $result = [];
    $stack = new SplStack();
    $stack->push($root);
    
    while (!$stack->isEmpty()) {
        $node = $stack->pop();
        $result[] = $node->value;
        
        if ($node->right !== null) {
            $stack->push($node->right);
        }
        if ($node->left !== null) {
            $stack->push($node->left);
        }
    }
    
    return $result;
}

Key Features:

• Uses SplStack for LIFO processing
• Immutable TreeNode class
• Explicit null checks
• Type-safe implementation
• Single responsibility function

Key Principles for Converting Recursive to Iterative

1. State Management

   • Use appropriate data structures (Stack/Queue) to maintain state
   • Choose between LIFO (Stack) and FIFO (Queue) based on traversal needs
   • Initialize all variables before use

2. Loop Structure

   • Replace recursive calls with while loops
   • Process items until the stack/queue is empty
   • Maximum nesting of two levels
   • Clear loop exit conditions

3. Error Handling

   • Validate inputs before processing
   • Use typed exceptions for error cases
   • No silent failures
   • Clear error messages

4. Performance Considerations

   • Prevents stack overflow for large datasets
   • More memory efficient than recursion
   • Predictable performance characteristics
   • Easier to debug and maintain

Benefits of Iterative Approach

1. Safety

   • No risk of stack overflow
   • Predictable memory usage
   • Type-safe implementations
   • Clear error boundaries

2. Maintainability

   • Easier to debug
   • More readable code flow
   • Simpler to modify
   • Better testability

3. Performance

   • Constant memory usage
   • No call stack overhead
   • Predictable execution time
   • Better cache utilization

4. Functional Programming

   • Pure functions
   • Predictable outputs
   • No side effects
   • Immutable data structures where possible

Best Practices

1. Always include strict types declaration
2. Use appropriate PHP 8+ features where available
3. Maintain single responsibility principle
4. Document edge cases and limitations
5. Include type hints for all parameters and returns
6. Use guard clauses for early validation
7. Maintain immutability where possible
8. Keep functions small and focused