Exploring Recursion with PHP | CodeSignal Learn

Exploring Recursion with PHP | CodeSignal Learn

Introduction

Hello, fellow explorer! Today, we will unravel the mystery of "Recursion" — a concept as enthralling as the patterns formed by two mirrors facing each other. We aim to decipher recursion, understand its inner workings, and master its application in programming.

Understanding Recursion

Consider a stack of books. Want the bottom one? You'll need to remove each book above it, one by one. It's a recurring action — an example of recursion. In programming, recursion involves a function calling itself repeatedly until a specific condition is met, similar to descending stairs one step at a time until you reach the ground. Here's a simple PHP function illustrating recursion: PHP<?php function recursiveFunction($x) { if($x <= 0){ // Termination condition --> base case echo "Base case reached\n"; } else { echo $x . PHP_EOL; recursiveFunction($x - 1); // Recursive function call --> recursive case } } recursiveFunction(5); /* Output: 5 4 3 2 1 Base case reached */ ?> This function keeps calling itself with $x decreasing by one until $x <= 0, which is our base case. At this point, it stops the recursion.

Defining the Base Case

The base case acts like a friendly signpost, telling the recursion when to stop. In our book stack example, reaching a point where no more books are left to remove serves as the signal. Similarly, $x <= 0 is our base case in our function. The base case is crucial as it prevents infinite recursion and related errors.

Defining the Recursive Case

Sign up

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

The recursive case is an essential aspect of recursion — the rule responsible for creating smaller versions of the original problem. Each call brings us a step closer to the base case. Let's use the process of calculating a factorial as an illustrative example.

To find a factorial, we multiply a number by the factorial of the number minus one and repeat this process until we get to one (our base case):

PHP

<?php
function factorial($n) {
  if($n == 1){ // base case
    return 1; 
  } else {
    return $n * factorial($n - 1); // recursive case
  }
}

echo factorial(3); // we expect 6 (3 * 2 * 1)
?>

In this case, when we call factorial(3), it returns 3 * factorial(2), where factorial(2) returns 2 * factorial(1). As factorial(1) is a base case, it returns 1. As a result, the whole recursion chain returns 3 * 2 * 1.

Another Example of Recursive Function

Let's develop a function that calculates the sum of an integer's digits. Normally, it would involve using a while loop, but with recursion, it is done much more easily: <?php function sumOfDigits($num) {// Base case: if num is less than 10, return num itself if($num < 10) {return $num;} else {return $num % 10 + sumOfDigits(intval($num / 10)); // Recursive case}} echo sumOfDigits(12345); // Will print out 15 (1+2+3+4+5) ?> In this example, we use the same principle as with factorial calculation, but we pass intval($num / 10) to the next recursion call, chopping off the last digit every time.

PHP

<?php
function sumOfDigits($num) {
  // Base case: if num is less than 10, return num itself
  if($num < 10) {
    return $num; 
  } else {
    return $num % 10 + sumOfDigits(intval($num / 10)); // Recursive case
  }
}

echo sumOfDigits(12345); // Will print out 15 (1+2+3+4+5)
?>