Section 11.9. Recursion

11.9. ^*Recursion

A function is recursive if it contains a call to itself. According to Aho, Sethi, and Ullman, "[a] procedure is recursive if a new activation can begin before an earlier activation of the same procedure has ended." In other words, a new invocation of the same function occurs within that function before it finished.

Recursion is used extensively in language recognition as well as in mathematical applications that use recursive functions. Earlier in this text, we took a first look at the factorial function where we defined:

N!  factorial(N)  1 * 2 * 3 ... * N

We can also look at factorial this way:

factorial(N) = N!              = N * (N-1)!              = N * (N-1) * (N-2)!                     :              = N * (N-1) * (N-2) ... * 3 * 2 * 1

We can now see that factorial is recursive because factorial(N) = N * factorial(N-1). In other words, to get the value of factorial(N), one needs to calculate factorial(N-1). Furthermore, to find factorial(N-1), one needs to computer factorial(N-2), and so on.

We now present the recursive version of the factorial function:

def factorial(n):     if n == 0 or n == 1: # 0! = 1! = 1         return 1    else:         return (n * factorial(n-1))