After the introductory article on recursive programming , it is time to see some practical examples.
Below you can see the most common examples used during programming training, coded in JavaScript, Python and PHP.
Before moving on to the codes, here is a curious fact about PHP:
The name “PHP” is a recursive acronym, which is an interesting curiosity in the world of computing. Originally, PHP stood for “Personal Home Page,” as it was created in 1994 by Rasmus Lerdorf as a set of simple tools to track visits to his personal web page. Over time, the language evolved and acquired many more features, becoming a full-fledged programming language.
As PHP grew in complexity and functionality, its name was changed to “PHP: Hypertext Preprocessor.” This is where recursion comes in: the acronym “PHP” includes the same “P” as “PHP,” which creates a logical loop. In other words, the meaning of the acronym PHP contains the name “PHP” itself, which gives rise to recursion in its name.
A recursive acronym is one in which one of the letters in the acronym refers to the acronym itself. This type of acronym is a kind of “inside joke” that reflects the programmers’ sense of humor and wit.
1. Factorial of a number
The factorial of a positive integer n is the product of all positive integers from 1 to n. It is denoted as n!
Python
def factorial(n):
if n == 0 or n == 1:
return 1
else:
return n * factorial(n - 1)
JavaScript
function factorial(n) {
if (n === 0 || n === 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}
PHP
function factorial($n) {
if ($n == 0 || $n == 1) {
return 1;
} else {
return $n * factorial($n - 1);
}
}
2. Fibonacci sequence
The Fibonacci sequence is a sequence of integers in which each number is the sum of the two preceding it. It typically begins with the numbers 0 and 1, and from there, each successive term is calculated as the sum of the two preceding numbers in the sequence.
Python
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)
JavaScript
function fibonacci(n) {
if (n === 0) {
return 0;
} else if (n === 1) {
return 1;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
PHP
function fibonacci($n) {
if ($n == 0) {
return 0;
} elseif ($n == 1) {
return 1;
} else {
return fibonacci($n - 1) + fibonacci($n - 2);
}
}
3. Binary search
Python
def binary_search(arr, target, low, high):
if low > high:
return -1
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] > target:
return binary_search(arr, target, low, mid - 1)
else:
return binary_search(arr, target, mid + 1, high)
JavaScript
function binarySearch(arr, target, low, high) {
if (low > high) {
return -1;
}
let mid = Math.floor((low + high) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] > target) {
return binarySearch(arr, target, low, mid - 1);
} else {
return binarySearch(arr, target, mid + 1, high);
}
}
PHP
function binarySearch($arr, $target, $low, $high) {
if ($low > $high) {
return -1;
}
$mid = floor(($low + $high) / 2);
if ($arr[$mid] == $target) {
return $mid;
} elseif ($arr[$mid] > $target) {
return binarySearch($arr, $target, $low, $mid - 1);
} else {
return binarySearch($arr, $target, $mid + 1, $high);
}
}
4. Towers of Hanoi
The Towers of Hanoi is a classic recursion problem that consists of moving n disks of different sizes from an initial pole to another, using a third auxiliary pole and following specific rules. The solution is based on dividing the problem into smaller subproblems, moving first the n-1 disks, then the largest disk, and finally the remaining n-1 disks, applying recursion at each step.
Python
def hanoi(n, source, target, auxiliary):
if n == 1:
print(f"Move disk 1 from {source} to {target}")
return
hanoi(n - 1, source, auxiliary, target)
print(f"Move disk {n} from {source} to {target}")
hanoi(n - 1, auxiliary, target, source)
JavaScript
function hanoi(n, source, target, auxiliary) {
if (n === 1) {
console.log(`Move disk 1 from ${source} to ${target}`);
return;
}
hanoi(n - 1, source, auxiliary, target);
console.log(`Move disk ${n} from ${source} to ${target}`);
hanoi(n - 1, auxiliary, target, source);
}
PHP
function hanoi($n, $source, $target, $auxiliary) {
if ($n == 1) {
echo "Move disk 1 from $source to $target\n";
return;
}
hanoi($n - 1, $source, $auxiliary, $target);
echo "Move disk $n from $source to $target\n";
hanoi($n - 1, $auxiliary, $target, $source);
}
5. Print a list in reverse
Python
def print_reverse(arr):
if len(arr) == 0:
return
print(arr[-1])
print_reverse(arr[:-1])
JavaScript
function printReverse(arr) {
if (arr.length === 0) {
return;
}
console.log(arr[arr.length - 1]);
printReverse(arr.slice(0, -1));
}
PHP
function printReverse($arr) {
if (count($arr) == 0) {
return;
}
echo array_pop($arr) . "\n";
printReverse($arr);
}
6. Add the elements of a list
Python
def sum_list(arr):
if len(arr) == 0:
return 0
else:
return arr[0] + sum_list(arr[1:])
JavaScript
function sumList(arr) {
if (arr.length === 0) {
return 0;
} else {
return arr[0] + sumList(arr.slice(1));
}
}
PHP
function sumList($arr) {
if (count($arr) == 0) {
return 0;
} else {
return array_shift($arr) + sumList($arr);
}
}
7. Permutations of a chain
Python
def permute(s, answer=''):
if len(s) == 0:
print(answer)
return
for i in range(len(s)):
ch = s[i]
left = s[:i]
right = s[i + 1:]
permute(left + right, answer + ch)
JavaScript
function permute(s, answer = '') {
if (s.length === 0) {
console.log(answer);
return;
}
for (let i = 0; i < s.length; i++) {
let ch = s[i];
let left = s.slice(0, i);
let right = s.slice(i + 1);
permute(left + right, answer + ch);
}
}
PHP
function permute($s, $answer = '') {
if (strlen($s) == 0) {
echo $answer . "\n";
return;
}
for ($i = 0; $i < strlen($s); $i++) {
$ch = $s[$i];
$left = substr($s, 0, $i);
$right = substr($s, $i + 1);
permute($left . $right, $answer . $ch);
}
}
We hope you liked it and don't forget to follow us on LinkedIN, where we announce each new article, and on the rest of the social networks where we will start to upload content about science but different.
https://www.linkedin.com/company/the-science-driven-company/
https://www.instagram.com/science.driven/