Lecture 16
Recursion
How would you code this problem? (regular way)
Method that returns TRUE if any element in the array is odd
Method that returns TRUE if any element in the array is odd
def anyOdd(lst):
for num in lst:
if num % 2 == 1:
return True
return False
anyOdd([2, 4, 6, 8])
Method that returns TRUE if any element in the array is odd
def anyOdd(lst):
for num in lst:
if num % 2 == 1:
return True
return False
anyOdd([2, 4, 6, 8])
We are going to solve this problem using recursion!
What is the Recursion?
Recursion: (1904) ->
https://en.wikipedia.org/wiki/Recursion
Recursion occurs when a thing is
defined in terms of itself
Droste effect
What is the Recursion?
Recursion: Why?
Recursive Functions
Definition: A function is called recursive if the body of that function calls itself
def print_me_again(x):
if (x == 0):
return
print(x)
print_me_again(x-1)
Get to a smaller problem
def anyOdd_2(lst):
if (lst[0] % 2 == 1):
return True
else:
smaller = lst[1:]
return anyOdd_2(smaller)
anyOdd_2([0, 4, 6, 8])
Will this code work?
A: Yes, always
B: Never
C: Sometimes
D: I have no idea
Fixed. Trace it
def anyOdd_3(lst):
if (len(lst) == 0): #added the base case
return False
elif (lst[0] % 2 == 1):
return True
else:
smaller = lst[1:]
return anyOdd_3(smaller)
anyOdd_3([2, 4, 6, 8])
Question
def hello(x):
print(x)
hello(x-1)
What happens if we call
hello(0)
A: Compiler error
B: 0
C: 0 -1 -2 -3 -4 …
D: 0 -1 -2 -3 -4….until crash
E: None of the above
Each number is on a new line ----->
Trace it + Demo
def hello(x):
print(x)
hello(x-1)
hello(0)
Recursion: Base case!
Question (X! = 1 * 2 * 3*...*X)
def fact(x):
if (x == 0):
_____________
else:
_________________
print(fact(5))
Fill in blanks (assume x is not negative)
A: return 0 fact(x)
B: return 1 return x * fact(x-1)
C: return 1 return (x-1) * fact(x-1)
D: return 0 return x * fact(x-1)
E: None of the above
Demo (with PythonTutor)
def fact(x):
if (x == 0):
return 1
else:
return x*fact(x-1)
print(fact(5))
Reminder/Announcements
Steps to design a recursive algorithm
Algorithmic steps
Let’s practice
Write a recursive method that calculates the product of a and b, where a and b are inputs that method. (a, b are positive ints)
Iterative solution:
def mult_it(a, b):
result = 0
while b > 0:
result = result + a
b = b - 1
return result
Recursive solution:
def mult_rec(a, b):
Let’s practice + env. diagram
Write a recursive method that calculates the product of a and b where a and b are positive ints.
Iterative solution:
def mult_it(a, b):
result = 0
while b>0:
result = result + a
b = b - 1
return result
Recursive solution:
def mult_rec(a, b):
if b==1:
return a
else:
return a+mult_rec(a, b-1)
Let’s practice
Given a non-negative int n, return the count of the occurrences of 9 as a digit.
def count_9s (number):
"""
>>> count_9s(919)
2
>>> count_9s(7)
0
>>> count_9s(129)
1
"""
# Base case. Think how many do you need.
Let’s practice
Given a non-negative int n, return the count of the occurrences of 9 as a digit.
def count_9s (number):
"""
>>> count_9s(919)
2
>>> count_9s(7)
0
>>> count_9s(129)
1
"""
# Base case. Think how many do you need.
if number == 9:
return 1
elif number < 9:
return 0
else:
What is your recursive step?
Let’s practice
Given a non-negative int n, return the count of the occurrences of 9 as a digit.
def count_9s (number):
"""
>>> count_9s(919)
2
>>> count_9s(7)
0
>>> count_9s(129)
1
"""
# Base case. Think how many do you need.
if number == 9:
return 1
elif number < 9:
return 0
else:
rem = number % 10
smaller = number //10
if (rem == 9):
return 1 + count_9s(smaller)
else:
return 0 + count_9s(smaller)
Let’s practice
problem
def count_9s (number):
"""
>>> count_9s(919)
2
>>> count_9s(7)
0
>>> count_9s(129)
1
"""
if number < 9:
return 0
else:
rem = number % 10
smaller = number //10
if (rem == 9):
return 1 + count_9s(smaller)
else:
return 0 + count_9s(smaller)
Check if a given string is a palindrome
def is_palindrome (input):
"""
>>> is_palindrome ('123321')
True
>>> is_palindrome('34554')
False
>>> is_palindrome('12321')
True
"""
# Base case
Check if a given string is a palindrome
def is_palindrome (input):
"""
>>> is_palindrome ('123321')
True
>>> is_palindrome('34554')
False
>>> is_palindrome('12321')
True
"""
# Base case
if len(input) == 0:
return True
Check if a given string is a palindrome
def is_palindrome (input):
"""
>>> is_palindrome ('123321')
True
>>> is_palindrome('34554')
False
>>> is_palindrome('12321')
True
"""
# Base case
if len(input) == 0:
return True
if len(input) == 1:
return True
# recursive step
Check if a given string is a palindrome
def is_palindrome (input):
"""
>>> is_palindrome ('123321')
True
>>> is_palindrome('34554')
False
>>> is_palindrome('12321')
True
"""
# Base case
if len(input) == 0:
return True
if len(input) == 1:
return True
# recursive step
else:
if input[0] == input[-1]:
?
Check if a given string is a palindrome
def is_palindrome (input):
"""
>>> is_palindrome ('123321')
True
>>> is_palindrome('34554')
False
>>> is_palindrome('12321')
True
"""
# Base case
if len(input) == 0:
return True
if len(input) == 1:
return True
# recursive step
else:
if input[0] == input[-1]:
return is_palindrome(input[1:-1])
else:
return False
Given a string, compute recursively the number of x characters in the string
def count_x (input):
"""
>>> count_x("xxhixx")
4
>>> count_x("xhixhix")
3
>>> count_x("hi")
0
"""
# base case?
Given a string, compute recursively the number of x characters in the string
def count_x (input):
"""
>>> count_x("xxhixx")
4
>>> count_x("xhixhix")
3
>>> count_x("hi")
0
"""
# base case?
if input == '': # if input is an empty string
return 0
else:
Given a string, compute recursively the number of x characters in the string
def count_x (input):
"""
>>> count_x("xxhixx")
4
>>> count_x("xhixhix")
3
>>> count_x("hi")
0
"""
# base case?
if input == '': # if input is an empty string
return 0
else:
if input[0] == 'x':
return 1 + count_x (input[1:])
Given a string, compute recursively the number of x characters in the string
def count_x (input):
"""
>>> count_x("xxhixx")
4
>>> count_x("xhixhix")
3
>>> count_x("hi")
0
"""
# base case?
counter = 0
if input == '': # if input is an empty string
return 0
else:
if input[0] == 'x':
return 1 + count_x (input[1:])
else:
return 0 + count_x (input[1:])
Trace it. Demo
def magic(x):
if (x>1):
magic(x-1)
print(x)
return None
magic(5)
What is the output?
A: 5
B: 5 4 3 2 1 #new line for each number
C: 1 2 3 4 5 #new line for each number
D: 1
E: Error or Infinite recursion
Trace it. Demo
def magic(x):
if (x>1):
print(x)
magic(x-1)
magic(5)
What is the output?
A: 5
B: 5 4 3 2 #new line for each number
C: 5 4 3 2 1 #new line for each number
D: 1 2 3 4 5 #new line for each number
E: 1
F: Error or Infinite recursion
Check point 1: print All odd numbers
def func(lst):
```
>>> func([3, 1, 2, 0])
3
1
```
if (len(lst) == 0):
return
else:
if (lst[0] % 2 == 1):
print(lst[0])
func(lst[1:])
else:
func(lst[1:])
Correct solution?
A: Yes for all inputs
B: Yes but for some inputs
C: Does not work for any input
Check point 2
def magic(lst):
if len(lst) == 0:
return []
return [lst[-1]] + magic(lst[:-1])
magic([1, 2, 3])
Purpose of the code?
A: Swap first and last elements in the list
B: Create a palindrome
C: Reverse a given list
D: Reverse the first half of the list
E: To confuse me
def magic(lst):
if len(lst) == 0:
return [ ]
return [lst[-1]] + magic(lst[:-1])
magic([1, 2, 3])
Practice if we have time. Classic question
Sum of Digits:
Create a recursive function that calculates the sum of the digits of a positive integer n.
For example, if n =123, the sum would be 1+2+3=6.
Practice if we have time.
Optional
Mutual Recursion
Tree Recursion
Types of Recursions
Direct Recursion
def function(x):
…
function(x-1)
…
Types of Recursions
Direct Recursion
def function(x):
…
function(x-1)
…
Indirect (or Mutual) Recursion
def function_a(x):
...
function_b(x-1)
...
def function_b(y):
...
function_a(y-2)
...
Classic example: even - odd
Classic example: even - odd
def is_even(n):
Classic example: even - odd
def is_even(n):
if n == 0:
return True
Classic example: even - odd
def is_even(n):
if n == 0:
return True
else:
return is_odd(n-1)
Classic example: even - odd
def is_even(n):
if n == 0:
return True
else:
return is_odd(n-1)
Classic example: even - odd
def is_even(n):
if n == 0:
return True
else:
return is_odd(n-1)
def is_odd(n):
if n == 0:
Classic example: even - odd
def is_even(n):
if n == 0:
return True
else:
return is_odd(n-1)
def is_odd(n):
if n == 0:
return False
else:
Classic example: even - odd
def is_even(n):
if n == 0:
return True
else:
return is_odd(n-1)
def is_odd(n):
if n == 0:
return False
else:
return is_even(n-1)
Let’s practice
Write two methods that calculate the following functions that are defined in terms of each other:
Let’s practice
Write two methods that calculate the following functions that are defined in terms of each other:
def A(x):
if x<= 1:
return 1
else:
return B(x+2)
def B(x):
return A(x-3) + 4
Tree recursion
Credit: J. DeNero
Tree recursion
Tree-shaped processes arise whenever executing the body of a recursive function makes more than one recursive call
Tree recursion
Tree-shaped processes arise whenever executing the body of a recursive function makes more than one recursive call
Tree recursion
Tree-shaped processes arise whenever executing the body of a recursive function makes more than one recursive call
Tree structure
Tree structure
Tree structure
Tree structure
Tree structure
Tree structure
Tree structure
Tree structure
Tree structure
Tree structure
Tree structure
Tree structure
Tree structure
Tree structure
Tree structure
Tree structure
Tree structure
Tree structure
Tree structure
Tree structure
Tree structure