Recursion refers to a way of defining things and a programming technique, not a language feature. Something that is recursive is defined at least partly in terms of itself. This seems impossible at first, but consider the case of a grocery list (not a Python list) of items:
milk, bread, coffee, sugar, peanut butter, cheese, jam
Each element in the list can be called an item, and represents something to be purchased at a grocery store. The smallest list is one having only a single element:
milk
Thus, a list can be simply an item. What else can it be? It appears to be several items separated by commas. One way to describe this is to say it can be an item followed by a comma followed by a list. The complete definition is, presuming that the symbol -> means “can be defined as,” is as follows:
list -> item # list can be defined as an item
list -> item, list # list can be defined as an item, a comma, and a list
In this way the list milk is defined as a list by the first rule. The list milk, bread is a list because it is an item (milk) followed by a comma followed by a list (bread). It is plain that a list is defined here in terms of itself, or at least in terms of a previous partial definition of itself.
When talking about functions, a function is recursive if it contains within it a call to itself. This is normally done only when the thing that it is attempting to accomplish has a definition that is recursive. Recursion as a programming technique is an attempt to make the solution simpler. If it does not, then it is inappropriate to use recursion. A problem some beginning programmers have with the ideas of a recursive function is that it appears that it does not terminate. Of course, it is essential that a function does return, and a program that never ends is almost always in error. The problem really is how to make certain that a chain of function calls terminates eventually.
The following function will never return once called:
def recurl (i)
recur1(i+1)
print (i)
It will not result in any output, either. Why not? Because the first thing it does is call itself, and always does so. When it does, the next thing is does is call itself again, and then again, and so on. The following function, on the other hand, does terminate:
def recur2 (i)
if i>0:
recur2(i-1)
print (i)
When called, it checks its parameter i. If that parameter is greater than zero, then it calls itself with a smaller value of i, meaning that eventually i will become smaller than 0 and the chain of calls will stop. What will be printed? The first call to recur2 that does not end up calling itself is when i==0, so the first thing printed is 0. Then the function returns to the previous recursive call, which had to be where i == 1. The second thing printed will be 1, and so on, until it returns to the original call to the function with the original value of i, at which point it prints i. This is a trivial example of a recursive function, but it illustrates how to exit from the chain of calls: there must be a condition that defines the recursion. When that condition fails, the recursion ceases.
Each call to the function can be thought of as an instance of that function, and it will create all of the local variables that are declared within it. Each instance has its own copy of these, including its parameters, and each call returns to the caller as occurs with any other function call. When the recursive call to recur2() returns, the next thing to be done is (in this case) to print the parameter value. A call to recur2() passing the parameter 4 results in the following instances of that function being created:
By tracing through the statements that are executed in this way, it can be seen that the recursion does end, and the output or result can be verified.
One important use of recursion is in reducing a problem into smaller parts, each of which has a simpler solution than does the whole problem. An example of this is searching a list for an item. If names = [Adams, Alira, Attenbourough, …] is a Python list of names in alphabetical order, answer the question: “Does the name Parker appear in this list?” There is a built-in function that does this, but this example is a good teaching tool. The built-in function may also be slower than the solution that is devised here.
The function will return True or False when passed a list and a name. The obvious way to solve the problem is to iterate through the list, looking at all of the elements until the name being searched for is either found or it is not possible to find it any more (i.e., the current name in the list is larger than the target name). Another, less obvious way to conduct the search is to divide the list in half, and only search the half that has the target name in it. Consider the following names in the list:
… Broadbent Butterworth Cait Cara Carling Devers Dillan Eberly Foxworthy …
The name in the middle if this list is Carling. If the name being searched for is lexicographically smaller than Carling, then it must appear in the first half; otherwise it must appear in the second half. That is, if it is there at all. A recursive example of an implementation of this is as follows:
If the name is in the list, this works fine. One way to think of this is that the function searchr() takes a string and a list as parameters and finds the name in the list if it’s there. The way it works is not clear from outside the function (without being able to see the source) and should not matter. If the target is to be found in the first half of the list, for example, then call searchr() with the first half of the list.
searchr (name, nameList[0:m])
The fact that the call is recursive is not really concerning. How can the problem of a name not being in the list be solved?
When the name is not in the list, the program will continue until there is but one item in the list. If that item is not the target, then it is not to be found. If n=1 (only one item in the list) and nameList[0] is not equal to the target, then the target is not found in the list and the return value is False. The final program is as follows:
def searchr (name, nameList):
n = len(nameList) # How many elements in this list?
m = int(n/2)
Many algorithms have fundamentally recursive implementations, meaning that the effective solution in the code involves a recursive function call. Many standard examples in beginning programming are not properly implemented recursively. Commonly encountered samples with a recursive solution include the factorial, which has a recursive definition but is not best implemented that manner, and any other basically linear technique (linear search, counting, and min/max finding) that does not do a reasonable subdivision. Testing the first component, for example, and then recursively looking at the remaining elements is a poor way to use recursion. It would be much better to use a loop. Let’s write an example: find the maximum value in a given list. The non-recursive method (reasonable) is as follows:
def max (myList):
max = myList [0]
for I in range(1, len(myList)):
if myList[i] > max:
max = myList[i]
return max
This is an effective way to find the largest value in a list and is easily understood by a programmer reading the code. Here is a recursive solution:
def maxr (myList):
ml = myList[0]
if len(myList)>1:
m2 = maxr (myList[1:])
else:
return ml
if ml > m2:
return ml
else:
return m2
This function works by subdividing the list into two parts, as is often done with a recursive solution. The idea is to compare the first element in the list with the maximum of the remainder of the list to see which is bigger. For this particular problem, this is not an obvious approach. It is less efficient and less obvious than the iterative version that preceded it. The use of recursion simplifies some problems, but it is not a universally applicable technique. Examples of useful recursive functions will be examined in later chapters.
1. Avoiding Infinite Recursion
There is a limit to how many times a function can call itself without returning, because each call uses up some amount of memory and memory is a finite resource. Usually, when this happens, a programming error has occurred and the function has slipped into an infinite recursion, in which it will continue to call itself without end. Recursion can be confusing to visualize and this sort of problem occurs frequently. How can it be avoided?
Programming the function correctly eliminates the problem, of course, but there are some basic rules that will avoid the problem at the early stages. Assuming that global variables are not being referenced:
- A function that begins with a call to itself is always infinitely recursive. The first thing the function does is call itself, and no matter what the parameters are, it can never end.
- Every recursive call within a function must have a condition upon which that call will be avoided. The function may return sometime before the call is made, or perhaps the call happens within an if statement, but there must be such a condition. If it exists, it is expressible as a Boolean expression, and this should be placed in a comment near the recursive call. The call is suspect until this happens.
- Avoid passing a function to itself. The call to a parameter hides the fact that recursion is taking place.
- It is possible to have a global variable that is a count of the depth of recursion. The function will increment this count whenever a recursive call is made and decrease it just before returning. If the count ever gets larger than a reasonable estimate of the maximum depth then the function could stop any more calls and back out, or an error message could be printed.
Source: Parker James R. (2021), Python: An Introduction to Programming, Mercury Learning and Information; Second edition.