Introduction to Python Programming

12.4More 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


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.

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.