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:

- factorial(0) = 1 (base case)
- factorial(n) = factorial(n-1) * n for n > 0 (recursive step)

```
<!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>
```

http://csci1101sp10.morris.umn.edu/~elenam/1101_spring10/recursion/factorial.php?n=10
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>
```

http://csci1101sp10.morris.umn.edu/~elenam/1101_spring10/recursion/array_sum.php
The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.