Recursion in PHP

Recursion is a programming technique where a function calls itself. Recursion is also a technique of “Making a loop in a functional way”. Recursive functions have two parts. “Base case” and “The Recursive function”.

Recursion in computer science is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem.

Wikipedia

Skeleton of a Recursive function:

function skeleton() {
 	// Base case
  
  	// Recursive function
}

Before we move forward, we need to know about Factorial.
It’s a mathematical term. The factorial of a positive integer n, denoted by n! and is the product of all positive integers less than or equal to n.
n! = n * (n – 1) * (n – 2) * (n – 3) * … .. * 3 * 2 * 1

Example: 5! = 5 * 4 * 3 * 2 * 1 = 120
Here,
5! = n!, n = 5, (n – 1) = 4, (n – 2) = 3, … ..

So, the factorial of 5 is 120. Here are a couple of things about factorial —

  • Can’t be a negative number
  • Factorial of 0 is equal to 1

Now let’s create a Recursive Function of Factorial

function fact($n) {
 	// Base case
  	if ( $n === 0 ) {
     	return 1;
    }
  
  	// recursive function
  	return $n * fact( $n - 1 );
}

echo fact(4); // 4 * 3 * 2 * 1 = 24

Now, you must be thinking, where is the loop? How it’s iterating and getting data?
The diagram down below will show the entire process of recursion.

Recursion-in-PHP

When I’ve called fact(4) it went into the function and got fact(3) and then it went into fact(3) and got fact(2)… .. and so on. Finally, it went to fact(0) and got 1 from the base case.

Then it started returning the value to fact(1), fact(2)… .. and so on, that’s why finally fact(4) got 6 from fact(3).

0 0 vote
Article Rating