A function is called recursive if the body of the function calls the function itself, either directly or indirectly. That is, the process of executing the body of a recursive function may in turn require applying that function again. Recursive functions do not use any special syntax in Python, but they do require some effort to understand and create.

We'll begin with an example problem: write a function that sums the digits of a natural number. When designing recursive functions, we look for ways in which a problem can be broken down into simpler problems. In this case, the operators % and // can be used to separate a number into two parts: its last digit and all but its last digit.

>>> 18117 % 10
7
>>> 18117 // 10
1811

The sum of the digits of 18117 is 1+8+1+1+7 = 18. Just as we can separate the number, we can separate this sum into the last digit, 7, and the sum of all but the last digit, 1+8+1+1 = 11. This separation gives us an algorithm: to sum the digits of a number n, add its last digit n % 10 to the sum of the digits of n // 10. There's one special case: if a number has only one digit, then the sum of its digits is itself. This algorithm can be implemented as a recursive function.

>>> def sum_digits(n):
        """Return the sum of the digits of positive integer n."""
        if n < 10:
            return n
        else:
            all_but_last, last = n // 10, n % 10
            return sum_digits(all_but_last) + last

Edit code in Online Python Tutor

This definition of sum_digits is both complete and correct, even though the sum_digits function is called within its own body. The problem of summing the digits of a number is broken down into two steps: summing all but the last digit, then adding the last digit. Both of these steps are simpler than the original problem. The function is recursive because the first step is the same kind of problem as the original problem. That is, sum_digits is exactly the function we need in order to implement sum_digits.

>>> sum_digits(9)
9
>>> sum_digits(18117)
18
>>> sum_digits(9437184)
36
>>> sum_digits(11408855402054064613470328848384)
126

We can understand precisely how this recursive function applies successfully using our environment model of computation. No new rules are required.

When the def statement is executed, the name sum_digits is bound to a new function, but the body of that function is not yet executed. Therefore, the circular nature of sum_digits is not a problem yet. Then, sum_digits is called on 738:

A local frame for sum_digits with n bound to 738 is created, and the body of sum_digits is executed in the environment that starts with that frame.
Since 738 is not less than 10, the assignment statement on line 4 is executed, splitting 738 into 73 and 8.
In the following return statement, sum_digits is called on 73, the value of all_but_last in the current environment.

Another local frame for sum_digits is created, this time with n bound to 73. The body of sum_digits is again executed in the new environment that starts with this frame.
Since 73 is also not less than 10, 73 is split into 7 and 3 and sum_digits is called on 7, the value of all_but_last evaluated in this frame.
A third local frame for sum_digits is created, with n bound to 7.
In the environment starting with this frame, it is true that n < 10, and therefore 7 is returned.
In the second local frame, this return value 7 is summed with 3, the value of last, to return 10.
In the first local frame, this return value 10 is summed with 8, the value of last, to return 18.

This recursive function applies correctly, despite its circular character, because it is applied twice, but with a different argument each time. Moreover, the second application was a simpler instance of the digit summing problem than the first. Generate the environment diagram for the call sum_digits(18117) to see that each successive call to sum_digits takes a smaller argument than the last, until eventually a single-digit input is reached.

This example also illustrates how functions with simple bodies can evolve complex computational processes by using recursion.

Building Abstractions with Functions

Original Chapter Link

Control

Defining New Functions

Designing Functions

Elements of Programming

Getting Started

Higher-Order Functions

Recursive Functions