Recursion refers to a programming approach in which a function works by calling itself. A recursive function must have a case when no more recursive calls are needed, this is called a base case. When writing a recursive function, make sure that its base case(s) is(are) reached to avoid an inifinite sequence of recursive calls.
A factorial is defined as:
<!DOCTYPE html
PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<!--
Recursive factorial
Author: Elena Machkasova elenam@morris.umn.edu
Last modified: 4/15/10
-->
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
<title>
CSci 1101: Recursive factorial
</title>
<?php
$n = $_GET["n"];
function factorial($n) {
if ($n == 0) return 1;
else return ($n * factorial($n-1));
}
?>
</head>
<body>
<p>
<?php
print "factorial(5)=".factorial(5)."<br />";
print "factorial($n)=".factorial($n)."<br />";
?>
</p>
</body>
</html>
The program shows a function that computes a sum of all numbers in an array that can have an arbitrary number of nested subarrays at any level of nesting. The way to distinguish a base case from a recursive step is to check if an array item is itself an array.
Note that in this case a loop solution is difficult to come up with. Recursion is a simple and natural approach to this problem.
<!DOCTYPE html
PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<!--
Recursive nested arrays
Author: Elena Machkasova elenam@morris.umn.edu
Last modified: 4/9/09
-->
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
<title>
CSci 1101: Recursive sum of a nested arrray
</title>
<?php
// the function is given an array that may
// contain nested subarrays. The function
// assumes that all arrays have only
// numbers in them. Arrays may be indexed
// in any way
function nested_array_sum($array) {
$sum = 0;
foreach($array as $item) {
// check if the item is an array
// recursive step (the item is itself an array):
if (is_array($item)) {
$sum = $sum + nested_array_sum($item);
}
// base case: the item is not an array, just add it to the sum
else $sum = $sum + $item;
}
return $sum;
}
?>
</head>
<body>
<?php
$numbers = array(2, array(7, 8), array(3, array(5, 6)), 6);
print "<pre>";
print_r($numbers);
print "</pre>";
print "<p>The sum of the nested array is: ".nested_array_sum($numbers)."</p>";
?>
</body>
</html>