11.3 Recursive Factorial Example

• Recursive problem-solving approaches have several elements in common
• A recursive function is 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
  • One that it does not know how to do
    • 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

11.3 Recursive Factorial Example (cont.)

• Recursion step executes while the original function call is still active (i.e., it has not finished executing)
  • Can result in many more recursive calls as the function divides each new subproblem into two conceptual pieces
• For recursion to terminate, 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

• Recursive factorial representation can be written as:

  n! = n · (n – 1)!

• 5! is equal to 5 · 4!, as in:

  5! = 5 · 4 · 3 · 2 · 1
  5! = 5 · (4 · 3 · 2 · 1)
  5! = 5 · (4!)

Visualizing Recursion

• Evaluation of 5! would proceed as shown below
• Left column shows how the succession of recursive calls proceeds until 1! (the base case) is evaluated to be 1
• 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

Implementing a Recursive Factorial Function

• Recursive function factorial first determines whether the terminating condition number <= 1 is True
• If True (the base case), factorial returns 1
  • 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)
  • Slightly smaller problem than the original calculation, factorial(number)
• Function factorial must receive a nonnegative argument

def factorial(number):
    """Return factorial of number."""
    if number <= 1:
        return 1
    return number * factorial(number - 1)  # recursive call

• Call factorial for the values 0-10
• Factorial values grow quickly
• Python does not limit the size of an integer, unlike many other programming languages

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

Indirect Recursion

• A recursive function may call another function, which may, in turn, make a call back to the recursive function
• Known as an indirect recursive call or indirect recursion

Stack Overflow and Infinite Recursion

• Amount of memory in a computer is finite, so only a certain amount of memory can be used to store activation records on the function-call 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
• Typically is the result of infinite recursion
  • Caused by omitting the base case or
  • writing the recursion step incorrectly so that it does not converge on the base case

Recursion and the Function-Call Stack

• “Functions” chapter introduced the function-call stack data structure
• That discussion also applies to recursive function calls
• Each recursive function call gets its own stack frame on the function-call stack
• When a given call completes, the system pops the function’s stack frame from the stack and control returns to the caller, possibly another copy of the same function

---

©1992–2020 by Pearson Education, Inc. All Rights Reserved. This content is based on Chapter 5 of the book Intro to Python for Computer Science and Data Science: Learning to Program with AI, Big Data and the Cloud.

DISCLAIMER: The authors and publisher of this book have used their best efforts in preparing the book. These efforts include the development, research, and testing of the theories and programs to determine their effectiveness. The authors and publisher make no warranty of any kind, expressed or implied, with regard to these programs or to the documentation contained in these books. The authors and publisher shall not be liable in any event for incidental or consequential damages in connection with, or arising out of, the furnishing, performance, or use of these programs.