Recursive functions
In mathematics, sequences are often recursively defined. For instance, the sequence of factorials n 7→
fn ≡ n! can be defined as
f0 = 1, ∀n>0 : fn = n × fn−1.
Instead of using a subscript, we write an argument in parentheses
F(n) = n × F(n − 1) if n > 0, otherwise 1
This is a form that can be translated into a C++ function. The header of a factorial function can look like:
int factorial(int n)
So what would the function body be? We need a return statement, and what we return should be n ×
F(n − 1):
int factorial(int n) {
return n*factorial(n-1);
} // almost correct, but not quite
So what happens if you write
int f3; f3 = factorial(3);
86 Introduction to Scientific Programming
7.5. Recursive functions
Well,
• The expression factorial(3) calls the factorial function, substituting 3 for the argument n.
• The return statement returns n*factorial(n-1), in this case 3*factorial(2).
• But what is factorial(2)? Evaluating that expression means that the factorial function is
called again, but now with n equal to 2.
• Evaluating factorial(2) returns 2*factorial(1),. . .
• . . . which returns 1*factorial(0),. . .
• . . . which returns . . .
• Uh oh. We forgot to include the case where n is zero. Let’s fix that:
int factorial(int n) {
if (n==0)
return 1;
else
return n*factorial(n-1);
}
• Now factorial(0) is 1, so factorial(1) is 1*factorial(0), which is 1,. . .
• . . . so factorial(2) is 2, and factorial(3) is 6.