RECURSION
Let’s write a program to perform a famous mathematical calculation. Consider the factorial of a positive integer n, which is written n! and pronounced “n factorial.” This is the product
View code image
n · (n – 1) · (n – 2) ··· 1
with 1! equal to 1 and 0! defined to be 1. For example, 5! is the product 5 · 4 · 3 · 2 · 1, which is equal to 120.
Iterative Factorial Approach
You can calculate 5! iteratively with a for statement, as in:
view code image
In [2]: for number in range(5, 0, 1):
...: factorial *= number
...:
In [3]: factorial
Out[3]: 120
Recursive Problem Solving
Recursive problemsolving approaches have several elements in common. When you call a recursive function to solve a problem, it’s actually capable of solving only the simplest case(s), or base case(s). If you call the function with a base case, it immediately returns a result. If you call the function with a more complex problem, it typically divides the problem into two pieces—one that the function knows how to do and one that it does not know how to do. To make recursion feasible, this latter piece must be a slightly simpler or smaller version of the original problem. Because this new problem resembles the original problem, the function calls a fresh copy of itself to work on the smaller problem—this is referred to as a recursive call and is also called the recursion step. This concept of separating the problem into two smaller portions is a form of the divide-and-conquer approach introduced earlier in the book.
The recursion step executes while the original function call is still active (i.e., it has not finished executing). It can result in many more recursive calls as the function divides each new subproblem into two conceptual pieces. For the recursion to eventually terminate, each time the function calls itself with a simpler version of the original problem, the sequence of smaller and smaller problems must converge on a base case. When the function recognizes the base case, it returns a result to the previous copy of the function. A sequence of returns ensues until the original function call returns the final result to the caller.
Recursive Factorial Approach
You can arrive at a recursive factorial representation by observing that n! can be written as:
View code image
For example, 5! is equal to 5 · 4!, as in:
5! = 5 · (4 · 3 · 2 · 1)
5! = 5 · (4!)
Visualizing Recursion
The evaluation of 5! would proceed as shown below. The left column shows how the succession of recursive calls proceeds until 1! (the base case) is evaluated to be 1, which terminates the recursion. The right column shows from bottom to top the values returned from each recursive call to its caller until the final value is calculated and returned.
 |
| By JuTT BaDshaH |
Implementing a Recursive Factorial Function
The following session uses recursion to calculate and display the factorials of the integers 0 through 10:
view code image
...: """Return factorial of number."""
...: if number <= 1:
...: return 1
...: return number * factorial(number 1) # recursive call
...:
In [5]: for i in range(11):
...: print(f'{i}! = {factorial(i)}')
...:
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
Snippet [4]’s recursive function factorial first determines whether the terminating condition number <= 1 is True. If this condition is True (the base case), factorial returns 1 and no further recursion is necessary. If number is greater than 1, the second return statement expresses the problem as the product of number and a recursive call to factorial that evaluates factorial(number 1). This is a slightly smaller problem than the original calculation, factorial(number). Note that function factorial must receive a nonnegative argument. We do not test for this case.
The loop in snippet [5] calls the factorial function for the values from 0 through 10. The output shows that factorial values grow quickly. Python does not limit the size of an integer, unlike many other programming languages.
Indirect Recursion
A recursive function may call another function, which may, in turn, make a call back to the recursive function. This is known as an indirect recursive call or indirect recursion. For example, function A calls function B, which makes a call back to function A. This is still recursion because the second call to function A is made while the first call to function A is active. That is, the first call to function A has not yet finished executing (because it is waiting on function B to return a result to it) and has not returned to function A’s original caller.
Stack Overflow and Infinite Recursion
Of course, the amount of memory in a computer is finite, so only a certain amount of memory can be used to store activation records on the functioncall stack. If more recursive function calls occur than can have their activation records stored on the stack, a fatal error known as stack overflow occurs. This typically is the result of infinite recursion, which can be caused by omitting the base case or writing the recursion step incorrectly so that it does not converge on the base case. This error is analogous to the problem of an infinite loop in an iterative (nonrecursive) solution.