Code’s way of solving problems within itself

Recursion is the last topic on PHP that we’ll cover before I make the switch to Laravel. Recursion is not a PHP topic, but I’ve been asked about it so frequently that I thought we would do an article on it. It has been a fun ride and thanks for reading along on this PHP series.

What is Recursion? You can get into the deep understanding of it, but for the sake of simplicity, it’s a function that calls itself from inside of the function body. In reality, it’s a way to solve a problem where the solution is generated from smaller problems using the function as the means of solving the problem.

Lets build a function that calls itself step by step.

In this example, we’ll create a function that accepts an integer. We’ll take each integer from 1 to n and add them together. We’ll return a responce once finished. Before we do that with a recursive function, lets do it with a for loop. So, if we say that n = 5 we’ll get 15 since 1 + 2 + 3 + 4 + 5 = 15.

<?php

// Result should be: 1 + 2 + 3 + 4 + 5 = 15
$sum = 0;
$n = 5;

for ($i = 1; $i <= $n; $i++) {
    $sum += $i;
}

var_dump($sum);

We can also go in the reverse order with our for loop.

<?php

// Result should be: 5 + 4 + 3 + 2 + 1 = 15
$sum = 0;
$n = 5;

for ($i = $n; $i > 0; $i--) {
    $sum += $i;
}

var_dump($sum);

Now that we can visualize that, we can start building our recursive function. Let’s do this one step at a time. First, lets create the function.

<?php

function recursiveSum( $n ) {
    // implement recursion
}

We know that our function needs to receive an argument, such as $n, that will need to add all of the integers from 1 to $n and return the sum.

I know what you’re thinking. Can we not just stuff the for loop into here? 🙂 Of course we can, but that’s not a recursive function.

If you’ve never seen a recursive function before, get ready to have your mind blown.

function recursiveSum( $n ) : int
{
    return $n + recursiveSum($n - 1);
}

What is going on here? Let’s just plug in a number and see what happens. Let’s start off with something small like $n = 3.

recursiveSum( 3 );
// return 3 + recursiveSum(3 - 1) OR return 3 + recursiveSum(2)
// We're now at $n = 2
recursiveSum( 2 );
// return 2 + recursiveSum(2 - 1) OR return 3 + recursiveSum(1)
// This is where we want to stop, but our function keeps going.

We’re still not ready to full walk through the example since the recursion never stops. It’ll keep going indefinitely, or until PHP times out. We need to put a stop to this. Which means, if we were to pass 1 as an argument, we don’t need to do anything; we just need to return 1 to the user. Anything less than 1 should be ignored. Let’s implement both of those checks.

function recursiveSum( $n ) : int
{
    if ($n < 1) {
        return 0;
    }

    if ($n == 1) {
        return 1;
    }

    return $n + recursiveSum($n - 1);
}

We could throw an error if someone enters something less than 1, but for the sake of simplicity, we’ll return 0. Let’s run through a couple of scenarios.

<?php

recursiveSum(0); // returns 0
recursiveSum(-42); // returns 0

Each of the above will return 0 since we check for it first and the function stops execution. Lets see what happens if we pass 1 exactly.

<?php

recursiveSum(1); // returns 1

In this instance, 1 is returned since the first check is skipped. Now, what happens when we pass 2?

recursiveSum(2);
// Skips both of the checks, since it passes both of them, and goes to the final step
// return 2 + recursiveSum(2 - 1) or return 2 + recursiveSum(1)
recursiveSum(1);
// We know what the recursiveSum of 1 is. We just did it, it's 1!
// Since 1 is returned we can now substitute recursiveSum(1) with 1
// i.e. return 2 + recursiveSum(1) EQUALS return 2 + 1;
// We get 3!

What if we went with 3 again as our argument.

recursiveSum(3)
  = 3 + recursiveSum(2)
    = 2 + recursiveSum(1)
    = 2 + 1
  = 3 + 3

recursiveSum(3);
// Skips both of the checks, since it passes both of them, and goes to the final step
// return 3 + recursiveSum(3 - 1) OR return 3 + recursiveSum(2)
recursiveSum(2);
// Skips both of the checks, since it passes both of them, and goes to the final step
// return 2 + recursiveSum(2 - 1) or return 2 + recursiveSum(1)
recursiveSum(1);
// We know what the recursiveSum of 1 is. We just did it, it's 1!
// Since 1 is returned we can now substitute recursiveSum(1) with 1
// i.e. return 2 + recursiveSum(1) EQUALS return 2 + 1;
// We now know what recursiveSum(2) equals. It's 3! We substitute recursiveSum(2) with 3
// i.e. return 3 + recursiveSum(2) EQUALS return 3 + 3
// We get 6!

I hope that you’re seeing how this goes layers deep. Another way to think about it is like this, if you’re still not getting it.

<?php

function one() {
    return 1;
}

function two() {
    return 2;
}

function three() {
    return 3;
}

$a = one() + two() + three();
var_dump($a);

In this example, we have three different functions: one, two and three. Each of those returns an integer value when evaluated. So $a = one() + two() + three(); yields 6. Let’s rewrite this slightly.

<?php

function one() {
    return 1;
}

function two() {
    return 2;
}

function three() {
    return 3;
}

function result () {
    return one() + two() + three();
}

$a = result();
var_dump($a);

The result function calls the other functions. Once they’re evaluated, they’re added together and the result is returned. So, what’s the difference if the function calls itself. Not much difference. This usually seems like the hardest concept to grasp, so let’s look at one more example. We’ll make the simplest function, called testFunction where it just returns the argument that was passed to it.

<?php

function testFunction($n) {
    return $n;
}

We could then pass different arguments to it and have it return different results. So, if we wanted to replicate our recursive functionality, we may do something like this.

function testFunction($n) {
    return $n;
}

$n = 3;
$result = testFunction($n) + testFunction($n - 1) + testFunction($n - 2);
var_dump($result);

What do we get?

testFunction($n)
   = testFunction(3)
   = 3

testFunction($n - 1)
   = testFunction(3 - 1)
   = testfunction(2)
   = 2

testFunction($n - 2)
   = testFunction(3 - 2)
   = testFunction(1)
   = 1

The result comes out to 3 + 2 + 1 = 6. I know that this is overkill at this point, but I hope that you’re seeing what happens when you call a function from within itself. It gets to a certain base case, and then returns. The result of that plus something else is returned again, and so on until you reach the top.

Look at this example again, and walk through it on your own. Write it out and you’ll see that it makes sense, if it hasn’t already.

function recursiveSum( $n ) : int
{
    if ($n < 1) {
        return 0;
    }

    if ($n == 1) {
        return 1;
    }

    return $n + recursiveSum($n - 1);
}

Palindrome Test

I think we’re ready to look at some examples. For the first example, let’s create a function called isPalindrome that tests to see if a string is a palindrome.

<?php

function isPalindrome($word) 
{
    if ( empty($word) ) {
        return true;
    }

    if ( $word[0] == $word[ strlen($word) - 1 ] ) {
        return isPalindrome( substr($word, 1, -1) );
    }

    return false;
}

var_dump( isPalindrome("") );
var_dump( isPalindrome("dino") );
var_dump( isPalindrome("dinoonid") );
var_dump( isPalindrome("dinonid") );
var_dump( isPalindrome("hello") );

Let’s walk through the examples.

isPalindrome("");
// enters the isPalindrome function.
// Since the argument $word is set to an empty string, we pass the first
// test: empty($word). Since it passes, it returns true.

isPalindrome("dino");
// enters the isPalindrome function
// It's not an empty string so it skips the first test: empty($word)
// Next, it checks whether the first character of the $word is equal to
// the last character in the $word. Since d does not equal o, it skips it.
// It sees false and returns false.

isPalindrome("dinoonid")
   = isPalindrome("inooni")
      = isPalindrome("noon")
         = isPalindrome("oo")
            = isPalindrome("")
            = true
         = true
      = true
   = true
= true 

• isPalindrome(“dinoonid”) enters the isPalindrome function.
• It’s not an empty string so it skips the first test: empty($word).
• Next, it checks whether the first character of the $word is equal to the last character in the $word.
• Since d equals d, it enters the body.
• We call the isPalindrome function again and pass it a substring.
• We eliminate the first character and the last character.
• We call, isPalindrome(“inooni”).
• It goes through the same process again, and calls isPalindrome(“noon”).
• It goes through the isPalindrome body and calls isPalindrome(“oo”).
• It goes through the isPalindrome body and calls isPalindrome(“”).
• This time it returns true. So, we know that isPalindrome(“”) is true.
• It returns up, so isPalindrome(“oo”) also returns true.
• Then it goes up again and  isPalindrome(“noon”) returns true.
• It goes up and returns true for isPalindrome(“inooni”).
• And finally, it returns true for isPalindrome(“dinoonid”).

I’ll let you walk through the other examples yourself.

Fibonacci Recursive Function

How about something simpler: the fibonacci. The fibonacci formula is Fn = Fn-2 + Fn-1. We usually know the first two fibonacci numbers, F0 = 1 and F1 = 1. Sometimes, F1 = 1 and F2 = 1. Fibonacci is a recursive function. We can say that:

• F(4) = F(4–2) + F(4–1)
• F(4) = F(2) + F(3)
• We know that F(2) = 1, so F(4) = 1 + F(3)
• F(4) = 1 + ( F(3–2) + F(3–1) )
• F(4) = 1 + ( F(1) + F(2) )
• We know that F(1) = 1 and F(2) also equals 1)
• F(4) = 1 + ( 1 + 1 )
• F(4) = 3

<?php

function fibonacci($num)
{
    if ($num <= 2) {
        return 1;
    }

    return fibonacci($num - 1) + fibonacci($num - 2);
}

var_dump(fibonacci(0));
var_dump(fibonacci(1));
var_dump(fibonacci(2));
var_dump(fibonacci(3));
var_dump(fibonacci(4));
var_dump(fibonacci(5));

In the fibonacci function, when we call fibonacci(0), fibonacci(1) and fibonacci(2), we pass the $num ≤ 2 test, which returns 1. So, lets walk through the next example: fibonacci(3).

fibonacci(3)
   = return fibonacci(2) + fibonacci(1)
   = return 1 + 1 = 2
= 2

How about the next one?

fibonacci(4)
   = return fibonacci(3) + fibonacci(2)
   = return fibonacci(3) + 1
      = (return fibonaci(2) + fibonacci(1)) + 1
   = (return 1 + 1) + 1
   = return 2 + 1
= 3

• We start by calling fibonacci(4)
• The first test is skipped since the $num = 4, which is greater than 2.
• We enter the return statement:
  return fibonacci($num — 1) + fibonacci($num-2)
return fibonacci(4-1) + fibonacci(4-2)
return fibonacci(3) + fibonacci(2)
• For fibonacci(3) we pass 3 as the argument. Since $num = 3 and is greater than our test value 2 we get to the next step:
  return fibonacci($num-1) + fibonacci($num-2)
return fibonacci(3-1) + fibonacci(3-2)
return fibonacci(2) + fibonacci(1)
• We’re going deep again. fibonacci(2) is called and it returns 1.
• We are now going to substitute fibonacci(2) with 1 and evaluate the next function:
  return 1 + fibonacci(1)
• We enter fibonacci(1) and it returns 1.
• We are now back to return 1 + fibonacci(1) and can substitute fibonacci(1) with 1:
  return 1 + 1;
• Where is this returned? It’s returned for fibonacci(3) for the following expression: return fibonacci(3) + fibonacci(2).
• So we get return 2 + fibonacci(2).
• We enter fibonacci(2) and we get 1.
• fibonacci(2) is substituted with 1:
  return 2 + fibonacci(2)
return 2 + 1
• The value 3 is returned for fibonacci(4).

There are so many interesting ways to use recursion. When I was writing my Algorithms book, it was difficult not to use recursion for most of the algorithms. For example, here’s the bubble sort algorithm:

<?php

function bubbleSort(&$sort, $length) {

    if ($length <= 1) {
        return;
    }

    for ( $i = 0; $i < $length - 1; $i++ ) {
        if ( $sort[$i] > $sort[$i + 1] ) {
            $temp         = $sort[$i];
            $sort[$i]     = $sort[$i + 1];
            $sort[$i + 1] = $temp;
        }
    }

    bubbleSort($sort, $length - 1);
}

$array = [78,39,14,56,88,94,108,5,15];
$length = count($array);

bubbleSort($array, $length);

var_dump($array);

I’ll let you figure that one out for yourself, or you can read the article on it here. It is written in Java, but same thing :).

Well that’s all folks. See you in Laravel land! It was fun creating this PHP article series. Hope you found it educational.

https://www.dinocajic.com/bubble-sort-algorithm-visually-explained/

https://github.com/dinocajic/php-youtube-tutorials