Recursions without Functions: with PHP

In the world of programming, recursion is often the go-to solution for tasks like factorial calculation, Fibonacci sequence, tree traversal, and more. However, if not properly Handled, recursion can lead to stack overflow errors when the depth becomes too deep, and function calls can be costly in terms of memory and performance, and there are cases where you may want to avoid using functions and just do your logic on the go.

This article explores how to achieve recursion-like behavior in PHP using stacks, loops, and goto— enabling us to solve common recursive problems without function calls, but before we start, I’d like to give a disclaimer: this isn’t an advocacy for or against recursive functions; it’s purely a knowledge-sharing exercise. Whether you prefer recursion or iteration often depends on the problem at hand, and knowing both techniques simply broadens your toolkit.

While there are several ways you can achieve this, in here we’ll just cover 3 ways you can use it, starting with.

1. Factorial Calculation Using a Stack

For the folks who were bad in Math just as I was, a factorial is the product of an integer and all the integers below it. For example, the factorial of 5 represents the multiplication of numbers 5, 4, 3, 2, 1 i.e 5!=5x4x3×2×1 which equal to 120.

And as for the stack, it’s an abstract data type that organizes items in a linear order, with new items added to the top and removed from the top

$n = 5;          // Number to calculate factorial for
$stack = [$n];   // Initialize stack with the starting number
$result = 1;

while (!empty($stack)) {
    $current = array_pop($stack);
    $result *= $current;

    if ($current > 1) {
        $stack[] = $current - 1;  // Push the next value onto the stack
    }
}

echo "Factorial of $n: $result\n";

Explanation:

• The stack here simulates the function calls in a typical recursive factorial function.
• We start by pushing the number onto the stack and then iterate, multiplying each value as we pop it from the stack.
• When we pop a number greater than 1, we push the next number (current - 1) onto the stack, continuing the process until we reach 1.

2. Tree Traversal Using a Stack (Depth-First Search)

In computeing, tree traversal refers to the process of visiting all the nodes in a tree structure, following a specific order. The depth-first search (DFS) strategy visits nodes starting from the root, and then explores as far as possible along each branch before backtracking.

Here, we perform tree traversal using a stack instead of recursion.

$tree = [
    'value' => 1,
    'left' => [
        'value' => 2,
        'left' => null,
        'right' => null
    ],
    'right' => [
        'value' => 3,
        'left' => null,
        'right' => null
    ]
];

$stack = [$tree];
$values = [];

while (!empty($stack)) {
    $node = array_pop($stack);
    if ($node === null) {
        continue;
    }
    
    $values[] = $node['value'];
    
    // Push right and left children onto the stack
    if (isset($node['right'])) $stack[] = $node['right'];
    if (isset($node['left'])) $stack[] = $node['left'];
}

echo "Depth-First Traversal: " . implode(', ', $values) . "\n";

Explanation:

• Nodes are pushed onto the stack and processed as we pop them. The right child is added first to ensure that the left child is processed first, following the depth-first order.
• The values of the nodes are collected as we visit each one.

3. Recursion Using goto : (Def not recommending this)

While not commonly used, PHP’s goto statement allows us to create a recursive-like flow by jumping back to a specific point in the code. Here's an example of using goto to simulate the factorial calculation in a way that mimics recursion.

$n = 5;  // Number to calculate factorial for
$result = 1;

start:
    if ($n <= 1) {
        echo "Factorial: $result\n";
        return;
    }

    $result *= $n;
    $n--;
    goto start;  // Jump back to the 'start' label to continue the "recursive" process

Explanation:

• The goto statement here simulates recursion by continuously jumping back to the start label as long as $n is greater than 1.
• In each iteration, we multiply $result by $n, then decrement $n and jump to the next iteration.
• Once $n reaches 1 or less, the process ends, and the factorial result is printed.

This example behaves similarly to a recursive function but relies on goto to jump back to the starting point, rather than making a function call.

Why Avoid goto?

While goto can work in specific situations, it's generally best avoided because it can lead to "spaghetti code," where the flow of execution becomes difficult to follow. Modern PHP coding standards encourage using loops and functions instead of goto for better code readability and maintainability.

All in all, there are multiple ways to simulate recursion in PHP without using traditional function calls or loops. You can achieve recursion-like behavior with:

• Generators, which yield results incrementally, simulating a recursive process.
• Closures, which can reference themselves and simulate recursion without a named function.

These techniques give you the flexibility to handle recursive problems in PHP while avoiding the overhead of function calls or the potential confusion caused by goto. Each method has its own advantages and is worth exploring depending on the complexity and needs of your application.