PHP Lessons - Lesson 9 - Recursion

In the previous lesson, we explored the use of functions in PHP. Now, we’ll dive deeper into how functions can be used. Previously, we used functions like this:

<?php
function myFunction() { // function declaration

}

$x = myFunction(); // function call
?>

But what happens if we call a function from within itself?

<?php
function myFunction() {
  $x = myFunction();
  ...
  return $x;
}

$y = myFunction();

This is called a recursive function call. While it may seem complex in theory, in practice it’s fairly straightforward.

Let’s write a recursive function that calculates exponentiation. From basic algebra, you might remember that raising a number to the power of n means multiplying that number by itself n times. In PHP, it can be implemented like this:

<?php
function myDegree($x, $n) {
  if ($n == 0) {
    return 1;
  }
  if ($n < 0) {
    return myDegree(1 / $x, -$n); // convert negative power to positive
  }
  return $x * myDegree($x, $n - 1); // recursive call
}

$y = myDegree(2, -4); // initial call
print $y;
?>

Let’s break this down:

• if ($n == 0): If the exponent is 0, return 1.
• if ($n < 0): For negative exponents, we convert the number to a fraction and the exponent to a positive.
• return $x * myDegree($x, $n - 1): For positive exponents, we recursively call the function and multiply the base.

Example step-by-step call for myDegree(2, -4):

1. Exponent -4, base 2 → Enter second if, becomes myDegree(0.5, 4)
2. Exponent 4, base 0.5 → Multiply 0.5 * myDegree(0.5, 3)
3. Exponent 3 → Multiply 0.5 * myDegree(0.5, 2)
4. Exponent 2 → Multiply 0.5 * myDegree(0.5, 1)
5. Exponent 1 → Multiply 0.5 * myDegree(0.5, 0)
6. Exponent 0 → Return 1 (base case)

The recursion ends, and all previous calls are resolved through multiplication.

Here’s another classic example: calculating a factorial. A factorial is the product of all positive integers from 1 to n. For example, 6! = 6*5*4*3*2*1 = 720. Again, we use recursion:

<?php
function myRecursion($x) {
  if ($x == 1) {
    return $x;
  }
  return $x * myRecursion($x - 1);
}

$y = myRecursion(8);
print $y;
?>

This is even simpler than the previous example. Try tracing the values of $x as the function recursively calls itself to understand the flow.