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

12.4 More math recursion

Introduction to Python Programming12.4 More math recursion

Learning objectives

By the end of this section you should be able to

  • Define a recursive function to generate Fibonacci numbers.

Fibonacci sequence using recursion

The Fibonacci sequence is a sequence in which each number in the sequence is the sum of the previous two numbers in the sequence. The first two numbers are 0 and 1. Thus, starting from 0 and 1, the third number is 0 + 1 = 1, and the next number is 1 + 1 = 2. The sequence of numbers is 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... .

Recursion can be used to calculate the nth Fibonacci number. The base cases are 0 and 1. Thereafter, the nth number is given by adding the (n - 1)th and (n - 2)th number. Thus, fib(n) = fib(n - 1) + fib(n - 2), which is a recursive definition ending with base cases f(0) = 0, and f(1) = 1.

For a recursion that calls multiple functions in the recursive case, tracing how the recursion proceeds is useful. A structure used to trace the calls made by a recursive function is called a recursion tree. The animation below traces the recursion tree for a call to a recursive function to calculate the Fibonacci number for n = 5.

Example 12.1

Finding the nth Fibonacci number

The Fibonacci function recursion is more complex with the value at n depending on two function calls with smaller values.

    """ Recursive Fibonacci function """

    def fib(n):
      # Base case
      if n == 0 or n == 1:
        return n
      # Recursive case
      elif n > 1:
        return fib(n - 1) + fib(n - 2)
      # Error case
      else:
        print("Fibonacci numbers begin at 0.")
        return

    # Test code
    print(fib(7))

The above code's output is:

    13
    

Checkpoint

Recursive Fibonacci function

Concepts in Practice

Fibonacci numbers

1.
fib(9) results in _____.
  1. 13
  2. 21
  3. 34
2.
How many calls to the base cases are made as a result of calling fib(5)?
  1. 2
  2. 5
  3. 8
3.
A structure tracing the function calls made as a result of a complex recursive function call is called a _____.
  1. tree
  2. recursion tree
  3. iteration tree

Greatest common divisor (GCD)

The greatest common divisor (GCD) of two positive integers is an integer that is a divisor for both integers. Ex: The GCD of 6 and 9 is 3 because 3 x 2 = 6, and 3 x 3 = 9.

The GCD is found easily using Euclid's method. Euclid's method recursively subtracts the smaller integer from the larger integer until a base case with equal integers is reached. The greatest common divisor is the integer value when the base case is reached.

Example 12.2

Finding the GCD

    """ Find GCD using recursive implementation of Euclid's method """

    def gcd(a, b):
      if a == b: # Base case
        return a
      elif a < b: # Recursive case
        return gcd(a, b - a)
      else:
        return gcd(a - b, a)

    # Test code
    print(gcd(24, 30))
    

The above code's output is:

    6
    

Concepts in Practice

GCD

4.
What is the GCD of 15 and 35?
  1. 15
  2. 20
  3. 5
5.
How many recursive calls are made with gcd(24, 30)?
  1. 4
  2. 1
  3. 24
6.
What is the GCD of 13 and 23?
  1. 13
  2. 1
  3. 23
7.
How many recursive calls are made with gcd(13, 23)?
  1. 1
  2. 8
  3. 13

Try It

Recursive power

Write a recursive power() function, such that given an integer x and a positive integer y, power(x, y) returns x raised to y.

Ex: power(3, 4) returns 81.

Try It

Recursive power (with any integer power)

Write a recursive rec_pow() function such that given two integers, x and y, it returns x raised to y.

(Note: this is an extension of the above problem but now works for any integer value of y, positive or negative. How should the recursive function change to deal with a negative value of y?)

Ex: rec_pow(2, -4) returns 0.0625.

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

© Feb 26, 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.