A recursive function is one where a function is defined in terms of itself.
Similar to higher-order functions except it returns a call to a function rather than the function itself
Will be hearing me talk about this a lot: recursive leap of faith
3 Steps of Recursion
Base Case
What is the smallest version of the problem we know the answer to?
I tend to think of this as the simplest input
Recursive Case (recursive call on a smaller version of the problem)
What can I do to reduce my input to something simpler?
Similar to while loops
Connecting it all together
Assuming your recursive call is correct (recursive leap of faith!), how do you solve the real problem
Example
deffactorial(n):if n == 0or n == 1: # Base Casereturn1else: # Recursive Casereturn n * factorial(n - 1)
Example
To calculate a factorial of an integer, what you do is multiply the integer itself with the factorial of one less than itself
factorial(5) = 5 * factorial(4)
Notice the recursive pattern - factorial(4) will call factorial(3), and so on and so forth, until our base case is reached.
We know the result of factorial(1), so calling factorial(1) will just return 1 (base case)
Example (Another Perspective)
What's the smallest input? What's the simplest problem I know the answer to?
0 is the smallest input - factorial(0) also returns 1.
How can I reduce my problem?
If you have factorial(n), you can reduce your problem down by calling factorial(n - 1).
In this step, you also assume your reduced problem gives you the correct answer (so factorial(n - 1) gives you the correct result - which is the recursive leap of faith)
How do I use that result to solve my problem?
Multiply by n
n * factorial(n - 1)
Recursion vs Iteration
Recursion
Iteration
Base case is needed for a recursive problem
A condition for a while loop is needed
Need to reduce down to the base case
Need to reduce down to the while condition
Can't use variables to keep track of values because they reset (need a helper function for that)
Can have variables to keep track of values.
Needs lots of frames - takes up memory
Loops happen in 1 frame
Recursion vs Iteration
# Recursiondeffactorial(n):if n == 0or n == 1:
return1else:
return n * factorial(n - 1)
# Iterationdeffactorial(n):
result = 1while n > 0:
result = result * n
n -= 1return result
Question 1 (Walkthrough)
Write a function that takes two numbers m and n and returns their product. Assume m and n are positive integers. Use recursion!
Hint: 5 * 3 = 5 + (5 * 2) = 5 + 5 + (5 * 1).
defmultiply(m, n):""" Takes two positive integers and returns their product using recursion.
>>> multiply(5, 3)
15
""""*** YOUR CODE HERE ***"
Question 1
Write a function that takes two numbers m and n and returns their product. Assume m and n are positive integers. Use recursion!
defmultiply(m, n):""" Takes two positive integers and returns their product using recursion.
>>> multiply(5, 3)
15
"""if n == 1: # Base casereturn m
else:
return m + multiply(m, n - 1) # Reducing case down
Question 2 (10 minutes)
Draw an environment diagram for the following code:
defrec(x, y):if y > 0:
return x * rec(x, y - 1)
return1
rec(3, 2)
Question 3
Find the bug with this recursive function.
defskip_mul(n):"""Return the product of n * (n - 2) * (n - 4) * ...
>>> skip_mul(5) # 5 * 3 * 1
15
>>> skip_mul(8) # 8 * 6 * 4 * 2
384
"""if n == 2:
return2else:
return n * skip_mul(n - 2)
Question 3
Find the bug with this recursive function.
defskip_mul(n):if n == 1:
return1if n == 2:
return2else:
return n * skip_mul(n - 2)
Question 5 (10 minutes)
Write a procedure merge(n1, n2) which takes numbers with digits in decreasing order and returns a single number with all the digits of the two, in decreasing order. Any number merged with 0 will be that number (treat 0 as having no digits). Use recursion.
defmerge(n1, n2):""" Merges two numbers by digit in decreasing order
>>> merge(31, 42)
4321
>>> merge(21, 0)
21
>>> merge (21, 31)
3211
""""*** YOUR CODE HERE ***"
Question 5
Write a procedure merge(n1, n2) which takes numbers with digits in decreasing order and returns a single number with all the digits of the two, in decreasing order. Any number merged with 0 will be that number (treat 0 as having no digits). Use recursion.
Write a function is_prime that takes a single argument n and returns True if n is a prime number and False otherwise. Assume n > 1. Use recursion. (Hint: You will need a helper function)
defis_prime(n):"""Returns True if n is a prime number and False otherwise.
>>> is_prime(2)
True
>>> is_prime(16)
False
>>> is_prime(521)
True
""""*** YOUR CODE HERE ***"
Question 6
Write a function is_prime that takes a single argument n and returns True if n is a prime number and False otherwise. Assume n > 1. Use recursion. (Hint: You will need a helper function)
defis_prime(n):defhelper(i):if i > (n ** 0.5):
returnTrueelif n % i == 0:
returnFalsereturn helper(i + 1)
return helper(2)
Question 4 (10 minutes)
Recall the hailstone function from Homework 2. First, pick a positive integer n as the start. If n is even, divide it by 2. If n is odd, multiply it by 3 and add 1. Repeat this process until n is 1. Write a recursive version of hailstone that prints out the values of the sequence and returns the number of steps.
defhailstone(n):"""Print out the hailstone sequence starting at n, and return the number of elements in the sequence.
>>> a = hailstone(10)
10
5
16
8
4
2
1
""""*** YOUR CODE HERE ***"
Question 4
defhailstone(n):print(n)
if n == 1:
return1if n % 2 == 0:
return1 + hailstone(n // 2)
else:
return1 + hailstone(n * 3 + 1)