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](https://blog.abmsourav.com/wp-content/uploads/2020/01/Recursion-in-PHP.png)
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)
.
Awesome post! Keep up the great work! 🙂
Great content! Super high-quality! Keep it up! 🙂