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/8/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 factorial
</title>
<?php
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(10)=".factorial(10)."<br />";
?>
</p>
</body>
</html>
http://csci1101sp09.morris.umn.edu/~elenam/1101_spring09/recursion/factorial.php
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 factorial
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>
http://csci1101sp09.morris.umn.edu/~elenam/1101_spring09/recursion/array_sum.php
<!DOCTYPE html
PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<!--
Recursive array printing - solution
Author: Elena Machkasova elenam@morris.umn.edu
Last modified: 4/21/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 array printing -- solution
</title>
<?php
// the function is given an array that may
// contain nested subarrays. The function
// prints the array elements indenting each level
function print_nested_array($array) {
foreach($array as $item) {
print "<div style=\"margin-left: 20px\">\n";
if (!is_array($item)) {
print $item;
} else {
print_nested_array($item);
}
print "</div>\n";
}
}
?>
</head>
<body>
<?php
$strings = array("Level one", array("Level two", "Another level two"),
array("Level two, second thread", array("Level three", "More level three")),
"Back to level one again");
//print "<pre>";
//print_r($strings);
//print "</pre>";
print_nested_array($strings);
?>
</body>
</html>
http://csci1101sp09.morris.umn.edu/~elenam/1101_spring09/recursion/array_printing_solution.php