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.

# A function does not need to call itself directly to be recursive; if it does so indirectly we can call this mutual recursion.

Share