Skip to ContentGo to accessibility pageKeyboard shortcuts menu
OpenStax Logo
Introduction to Python Programming

12.2 Simple 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.

Checkpoint

Finding the factorial of 5

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.

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?

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.

Citation/Attribution

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.

Attribution information
  • If you are redistributing all or part of this book in a print format, then you must include on every physical page the following attribution:
    Access for free at https://openstax.org/books/introduction-python-programming/pages/1-introduction
  • If you are redistributing all or part of this book in a digital format, then you must include on every digital page view the following attribution:
    Access for free at https://openstax.org/books/introduction-python-programming/pages/1-introduction
Citation information

© Jul 30, 2024 OpenStax. Textbook content produced by OpenStax is licensed under a Creative Commons Attribution License . The OpenStax name, OpenStax logo, OpenStax book covers, OpenStax CNX name, and OpenStax CNX logo are not subject to the Creative Commons license and may not be reproduced without the prior and express written consent of Rice University.

This book utilizes the OpenStax Python Code Runner. The code runner is developed by Wiley and is All Rights Reserved.