12.2: Simple Math Recursion

Learning Objectives

By the end of this section you should be able to

• Identify a recursive case and a base case in a recursive algorithm.
• Demonstrate how to compute a recursive solution for the factorial function.

Calculating a factorial

The factorial of a positive integer is defined as the product of the integer and the positive integers less than the integer.

Ex: 5! = 5 * 4 * 3 * 2 * 1

Written as a general equation for a positive integer n: n! = n * (n - 1) * (n - 2) * . . . * 1

The above formula for the factorial of n results in a recursive formula: n! = n * (n - 1)!

Thus, the factorial of n depends upon the value of the factorial at n - 1. The factorial of n can be found by repeating the factorial of n - 1 until (n - 1)! = 1! (we know that 1! = 1). This result can be used to build the overall solution as seen in the animation below.

Checkpoint: Finding the factorial of 5

Concepts in Practice \(\PageIndex{1}\): Recognizing recursion

Can the following algorithm be written recursively? The summation of 1 + 2 + 3 + . . . + (n - 1) + n where n is a positive integer.

Answer

The summation can be calculated using recursion because there is a regular pattern and the summation to n depends on the summation to n - 1.

Concepts in Practice \(\PageIndex{2}\): Recognizing recursion

Can the following algorithm be written recursively? Listing the odd numbers greater than 0 and less than a given number n.

Answer

Each number in the sequence can be found by adding 2 to the previous number, with the solution at 1 being 1 .

Concepts in Practice \(\PageIndex{3}\): Recognizing recursion

Can the following algorithm be written recursively? Listing the primary numbers (prime numbers) greater than 3.

Answer

A prime number does not depend on a smaller prime number; thus, no recursion can be found to generate new prime numbers based on an existing list of prime numbers.

Concepts in Practice \(\PageIndex{4}\): Recognizing recursion

Can the following algorithm be written recursively? Listing the Fibonacci sequence of numbers.

Answer

A given number in the Fibonacci sequence is found by summing the previous two numbers in the sequence, so the Fibonacci sequence can be found recursively.

Defining a recursive function

Recursive algorithms are written in Python as functions. In a recursive function different actions are performed according to the input parameter value. A critical part of a recursive function is that the function must call itself.

A value for which the recursion applies is called the recursive case. In the recursive case, the function calls itself with a smaller portion of the input parameter. Ex: In the recursive function factorial(), the initial parameter is an integer n. In the function's recursive case, the argument passed to factorial() is n - 1, which is smaller than n.

A value of n for which the solution is known is called the base case. The base case stops the recursion. A recursive algorithm must include a base case; otherwise, the algorithm may result in an infinite computation.

To calculate a factorial, a recursive function, factorial() is defined with an integer input parameter, n. When n > 1, the recursive case applies. The factorial() calls itself with a smaller argument, n - 1. When n == 1, the solution is known because 1! is 1; therefore, n == 1 is a base case.

Note: 0! is defined to be 1; therefore, n == 0 is a second base case for factorial(). When n < 1, an error is returned.

Checkpoint: Factorial using recursion

Concepts in Practice: Programming recursion

For the questions below, the function rec_fact() is another recursive function that calculates a factorial. What is the result of each definition of rec_fact() if n = 17 is the initial input parameter?

Concepts in Practice \(\PageIndex{5}\): Programming recursion

def rec_fact(n):
  return n * rec_fact(n - 1)

1. 355687428096000
2. 0
3. no result / infinite computation

Answer

c. There is a missing base case, so there is no place for the recursion to end.

Concepts in Practice \(\PageIndex{6}\): Programming recursion

def rec_fact(n):
  if n < 0:
    print("error")
  elif n == 0:
    return n
  else:
    return n * rec_fact(n - 1)

1. 355687428096000
2. 0
3. no result / infinite computation

Answer

b. This definition of rec_fact() uses a base case of n == 0, which works because, just like 1!, 0! = 1. However, the base case of n == 0 returns n, which at this stage is 0 , and therefore zeroes out the rest of the computation.

Concepts in Practice \(\PageIndex{7}\): Programming recursion

def rec_fact(n):
  if n < 0:
    print("error")
  elif n == 0:
    return 1
  else:
    return n * rec_fact(n - 1)

1. 355687428096000
2. 0
3. no result / infinite computation

Answer

a. The recursive function begins returning correctly at the base case of n == 0. 0! = 1.

Concepts in Practice \(\PageIndex{8}\): Programming recursion

def rec_fact(n):
  if n < 0:
    return -1
  else:
    return n * rec_fact(n - 1)

1. 355687428096000
2. 0
3. no result / infinite computation

Answer

b. The base case of n == 1 is not used in the function. When n is 0 , the overall multiplication becomes 0 . The recursion begins returning once the n < 0 base case is reached, initially returning -1. But the previous recursive call would return 0 , thereby zeroing out all computations and leaving an overall result of 0 .

Try It: Recursive summation

Write a program that uses a recursive function to calculate the summation of numbers from 0 to a user specified positive integer n.

Interactive Code

Input

5

Answer

# Define the recursive function to calculate the summation
def rec_sum(n):
if n < 0:
print("The summation is not defined for negative integers.")
return -1
elif n == 0: # Base case
return 0
else:
return n + rec_sum(n-1)

# Take the input from the user
n = int(input())

# Call the recursive function
print(rec_sum(n))

Try It: Digits

Write a program that computes the sum of the digits of a positive integer using recursion.

Ex: The sum of the digits of 6721 is 16.

Hint: There are 10 base cases, which can be checked easily with the right condition.

Interactive Code

Input

6721

Answer

# Define the recursive function to calculate the summation
def digit_sum(n):
if n < 0:
print("The summation is not defined for negative integers.")
return -1
elif n < 10: # Base case for single digit numbers
return n
else:
return n%10 + digit_sum(n//10)

# Take the input from the user
n = int(input())

# Call the recursive function
print(digit_sum(n))