Algoritmos recursivos más comunes en JavaScript, Python y PHP

Most common recursive algorithms in JavaScript, Python and PHP

After the introductory article on recursive programming , it is time to see some practical examples.

Below you can see the most common examples used during programming training, coded in JavaScript, Python and PHP.

Before moving on to the codes, here is a curious fact about PHP:

The name “PHP” is a recursive acronym, which is an interesting curiosity in the world of computing. Originally, PHP stood for “Personal Home Page,” as it was created in 1994 by Rasmus Lerdorf as a set of simple tools to track visits to his personal web page. Over time, the language evolved and acquired many more features, becoming a full-fledged programming language.

As PHP grew in complexity and functionality, its name was changed to “PHP: Hypertext Preprocessor.” This is where recursion comes in: the acronym “PHP” includes the same “P” as “PHP,” which creates a logical loop. In other words, the meaning of the acronym PHP contains the name “PHP” itself, which gives rise to recursion in its name.

A recursive acronym is one in which one of the letters in the acronym refers to the acronym itself. This type of acronym is a kind of “inside joke” that reflects the programmers’ sense of humor and wit.

1. Factorial of a number

The factorial of a positive integer n is the product of all positive integers from 1 to n. It is denoted as n!

Python


def factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n - 1)

JavaScript


function factorial(n) {
    if (n === 0 || n === 1) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

PHP


function factorial($n) {
    if ($n == 0 || $n == 1) {
        return 1;
    } else {
        return $n * factorial($n - 1);
    }
}

2. Fibonacci sequence

The Fibonacci sequence is a sequence of integers in which each number is the sum of the two preceding it. It typically begins with the numbers 0 and 1, and from there, each successive term is calculated as the sum of the two preceding numbers in the sequence.

Python


def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

JavaScript


function fibonacci(n) {
    if (n === 0) {
        return 0;
    } else if (n === 1) {
        return 1;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

PHP


function fibonacci($n) {
    if ($n == 0) {
        return 0;
    } elseif ($n == 1) {
        return 1;
    } else {
        return fibonacci($n - 1) + fibonacci($n - 2);
    }
}

3. Binary search

Python


def binary_search(arr, target, low, high):
    if low > high:
        return -1
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return binary_search(arr, target, low, mid - 1)
    else:
        return binary_search(arr, target, mid + 1, high)

JavaScript


function binarySearch(arr, target, low, high) {
    if (low > high) {
        return -1;
    }
    let mid = Math.floor((low + high) / 2);
    if (arr[mid] === target) {
        return mid;
    } else if (arr[mid] > target) {
        return binarySearch(arr, target, low, mid - 1);
    } else {
        return binarySearch(arr, target, mid + 1, high);
    }
}

PHP


function binarySearch($arr, $target, $low, $high) {
    if ($low > $high) {
        return -1;
    }
    $mid = floor(($low + $high) / 2);
    if ($arr[$mid] == $target) {
        return $mid;
    } elseif ($arr[$mid] > $target) {
        return binarySearch($arr, $target, $low, $mid - 1);
    } else {
        return binarySearch($arr, $target, $mid + 1, $high);
    }
}

4. Towers of Hanoi

The Towers of Hanoi is a classic recursion problem that consists of moving n disks of different sizes from an initial pole to another, using a third auxiliary pole and following specific rules. The solution is based on dividing the problem into smaller subproblems, moving first the n-1 disks, then the largest disk, and finally the remaining n-1 disks, applying recursion at each step.

Python


def hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    hanoi(n - 1, source, auxiliary, target)
    print(f"Move disk {n} from {source} to {target}")
    hanoi(n - 1, auxiliary, target, source)

JavaScript


function hanoi(n, source, target, auxiliary) {
    if (n === 1) {
        console.log(`Move disk 1 from ${source} to ${target}`);
        return;
    }
    hanoi(n - 1, source, auxiliary, target);
    console.log(`Move disk ${n} from ${source} to ${target}`);
    hanoi(n - 1, auxiliary, target, source);
}

PHP


function hanoi($n, $source, $target, $auxiliary) {
    if ($n == 1) {
        echo "Move disk 1 from $source to $target\n";
        return;
    }
    hanoi($n - 1, $source, $auxiliary, $target);
    echo "Move disk $n from $source to $target\n";
    hanoi($n - 1, $auxiliary, $target, $source);
}

5. Print a list in reverse

Python


def print_reverse(arr):
    if len(arr) == 0:
        return
    print(arr[-1])
    print_reverse(arr[:-1])

JavaScript


function printReverse(arr) {
    if (arr.length === 0) {
        return;
    }
    console.log(arr[arr.length - 1]);
    printReverse(arr.slice(0, -1));
}

PHP


function printReverse($arr) {
    if (count($arr) == 0) {
        return;
    }
    echo array_pop($arr) . "\n";
    printReverse($arr);
}

6. Add the elements of a list

Python


def sum_list(arr):
    if len(arr) == 0:
        return 0
    else:
        return arr[0] + sum_list(arr[1:])

JavaScript


function sumList(arr) {
    if (arr.length === 0) {
        return 0;
    } else {
        return arr[0] + sumList(arr.slice(1));
    }
}

PHP


function sumList($arr) {
    if (count($arr) == 0) {
        return 0;
    } else {
        return array_shift($arr) + sumList($arr);
    }
}

7. Permutations of a chain

Python


def permute(s, answer=''):
    if len(s) == 0:
        print(answer)
        return
    for i in range(len(s)):
        ch = s[i]
        left = s[:i]
        right = s[i + 1:]
        permute(left + right, answer + ch)

JavaScript


function permute(s, answer = '') {
    if (s.length === 0) {
        console.log(answer);
        return;
    }
    for (let i = 0; i < s.length; i++) {
        let ch = s[i];
        let left = s.slice(0, i);
        let right = s.slice(i + 1);
        permute(left + right, answer + ch);
    }
}

PHP


function permute($s, $answer = '') {
    if (strlen($s) == 0) {
        echo $answer . "\n";
        return;
    }
    for ($i = 0; $i < strlen($s); $i++) {
        $ch = $s[$i];
        $left = substr($s, 0, $i);
        $right = substr($s, $i + 1);
        permute($left . $right, $answer . $ch);
    }
}

Frequently asked questions about recursive algorithms in JavaScript, Python and PHP

What are common examples of recursive algorithms?

Common recursive algorithms include factorial, the Fibonacci sequence, binary search, the Tower of Hanoi, summing or reversing a list and generating permutations of a string. In production code, recursion shows up in merge sort, quicksort, tree traversal, depth-first search on graphs and parsers for nested data such as JSON or HTML. Each one has a base case and a step that shrinks the problem.

How do you write a recursive function in Python?

You write a recursive function in Python with def, a base case that returns a value directly and a call to the same function with a smaller argument. A factorial needs only "if n <= 1 return 1" followed by "return n * factorial(n - 1)". Keep in mind that Python does not optimize tail calls and stops at 1,000 nested calls by default.

What is the maximum recursion depth in Python?

The default maximum recursion depth in Python is 1,000 nested calls. Past that limit the interpreter raises RecursionError so the program does not crash the underlying C stack. You can read the limit with sys.getrecursionlimit() and raise it with sys.setrecursionlimit(), but setting it too high can crash the process outright. For very deep inputs, rewriting the algorithm with a loop or an explicit stack is the safer fix.

What does "Maximum call stack size exceeded" mean in JavaScript?

This error means a chain of function calls, usually a recursion without a reachable base case, has filled the call stack. Chrome and Node.js throw it as a RangeError. The exact depth limit depends on the engine and available memory and typically falls in the thousands to tens of thousands of calls. ES2015 specified proper tail calls, yet Safari is the only major browser that implements them.

Does PHP have a recursion limit?

PHP has no fixed cap on the number of recursive calls the way Python does. The real ceiling is the available memory and the size of the system stack. Starting with PHP 8.3, the engine detects when the stack is nearly full and throws a catchable Error so the process does not simply crash. Debugging tools such as Xdebug add their own nesting limit, which you can set in php.ini.

What does PHP stand for?

PHP stands for "PHP: Hypertext Preprocessor", a recursive acronym because the abbreviation appears inside its own definition. Rasmus Lerdorf started the project in 1994 and released it in 1995 as Personal Home Page Tools. The recursive name arrived with PHP 3 in 1998. Programmers love this kind of joke, and GNU, short for "GNU's Not Unix", is the best known example.

How many moves does the Tower of Hanoi take?

The Tower of Hanoi with n disks takes a minimum of 2^n − 1 moves. The recursive solution moves n − 1 disks to the spare peg, moves the largest disk to the target and then stacks the n − 1 disks back on top. Three disks take 7 moves. The 64 disks of the legend would take about 1.8 × 10^19 moves, more than 580 billion years at one move per second.

Why is recursive Fibonacci so slow?

Naive recursive Fibonacci is slow because it recomputes the same values over and over. Computing F(40) this way takes more than 331 million function calls. The count grows exponentially with n. Memoization, which caches results already computed, cuts the work to a few dozen steps. It is the classic proof that algorithm design matters more than raw hardware speed.

Back to blog

Leave a comment