Core Python Programming

11.9. *Recursion

A function is recursive if it contains a call to itself. Aho, Sethi, and Ullman define, “[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 ...