Introduction to Python Programming

# 12.2Simple math recursion

Introduction to Python Programming12.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.

## Concepts in Practice

### Recognizing recursion

Can the following algorithms be written recursively?

1.
The summation of 1 + 2 + 3 + . . . + (n - 1) + n where n is a positive integer.
2.
Listing the odd numbers greater than 0 and less than a given number n.
3.
Listing the primary numbers (prime numbers) greater than 3.
4.
Listing the Fibonacci sequence of numbers.

## 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.

## 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?

5.
def rec_fact(n):
return n * rec_fact(n - 1)
1. 355687428096000
2. 0
3. no result / infinite computation
6.
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
7.
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
8.
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

## 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.

## 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.

This book may not be used in the training of large language models or otherwise be ingested into large language models or generative AI offerings without OpenStax's permission.

Want to cite, share, or modify this book? This book uses the Creative Commons Attribution License and you must attribute OpenStax.