RECURSION
(download slides and .py files to follow along)
6.100L Lecture 15
Ana Bell
1
ITERATIVE ALGORITHMS
SO FAR
Looping constructs (while and for loops) lead to
iterative algorithms
Can capture computation in a set of state variables that
update, based on a set of rules, on each iteration through
loop
What is changing each time through loop, and how?
How do I keep track of number of times through loop?
When can I stop?
Where is the result when I stop?
6.100L Lecture 15
MULTIPLICATION
The * operator does this for us
Make a function
def mult(a, b):
return a*b
6.100L Lecture 15
MULTIPLICATION
THINK in TERMS of ITERATION
Can you make this iterative?
Define a*b as a+a+a+a... b times
Write a function
def mult(a, b):
total = 0
for n in range(b):
total += a
return total
6.100L Lecture 15
MULTIPLICATION –
ANOTHER ITERATIVE SOLUTION
“multiply a * b” is equivalent to “add b copies of a”
a + a + a + a + … + a
Capture state by i i i i i
An iteration number (i) starts at b result: 0 result:
result: 2a result:
a result: 3a 4a
Update i i-1 and stop when 0
rules
A current value of computation (result) starts at 0
result result + a
def mult_iter(a, b):
result = 0
while b > 0:
result += a
b -= 1
return result
5
6.100L Lecture 15
MULTIPLICATION
NOTICE the RECURSIVE PATTERNS
Recognize that we have a problem we are solving many times
If a = 5 and b = 4
5*4 is 5+5+5+5
Decompose the original problem into
Something you know and
the same problem again
Original problem is using * between two numbers
5*4 is 5+5*3
But this is 5+5+5*2
And this is 5+5+5+5*1
6.100L Lecture 15
MULTIPLICATION
FIND SMALLER VERSIONS of the PROBLEM
Recognize that we have a problem we are solving many times
If a = 5 and b = 4
5*4 is 5+5+5+5
Decompose the original problem into
Something you know and
the same problem again
Original problem is using * between two numbers
5*4
= 5+( 5*3 )
= 5+(5+( 5*2 ))
= 5+(5+(5+(5*1)))
6.100L Lecture 15
MULTIPLICATION
FIND SMALLER VERSIONS of the PROBLEM
Recognize that we have a problem we are solving many times
If a = 5 and b = 4
5*4 is 5+5+5+5
Decompose the original problem into
Something you know and
the same problem again
Original problem is using * between two numbers
5*4
= 5+( 5*3 )
= 5+(5+( 5*2 ))
= 5+(5+(5+(5*1)))
6.100L Lecture 15
MULTIPLICATION
FIND SMALLER VERSIONS of the PROBLEM
Recognize that we have a problem we are solving many times
If a = 5 and b = 4
5*4 is 5+5+5+5
Decompose the original problem into
Something you know and
the same problem again
Original problem is using * between two numbers
5*4
= 5+( 5*3 )
= 5+(5+( 5*2 ))
= 5+(5+(5+(5*1)))
6.100L Lecture 15
MULTIPLICATION
REACHED the END
Recognize that we have a problem we are solving many times
If a = 5 and b = 4
5*4 is 5+5+5+5
Decompose the original problem into
Something you know and
the same problem again
Original problem is using * between two numbers
5*4
= 5+( 5*3 )
= 5+(5+( 5*2 ))
= 5+(5+(5+(5*1)))
10
6.100L Lecture 15
MULTIPLICATION
BUILD the RESULT BACK UP
Recognize that we have a problem we are solving many times
If a = 5 and b = 4
5*4 is 5+5+5+5
Decompose the original problem into
Something you know and
the same problem again
Original problem is using * between two numbers
5*4
= 5+( 5*3 )
= 5+(5+( 5*2 ))
= 5+(5+(5+( 5 )))
11
6.100L Lecture 15
MULTIPLICATION
BUILD the RESULT BACK UP
Recognize that we have a problem we are solving many times
If a = 5 and b = 4
5*4 is 5+5+5+5
Decompose the original problem into
Something you know and
the same problem again
Original problem is using * between two numbers
5*4
= 5+( 5*3 )
= 5+(5+( 10 ))
= 5+(5+(5+( 5 )))
12
6.100L Lecture 15
MULTIPLICATION
BUILD the RESULT BACK UP
Recognize that we have a problem we are solving many times
If a = 5 and b = 4
5*4 is 5+5+5+5
Decompose the original problem into
Something you know and
the same problem again
Original problem is using * between two numbers
5*4
= 5+( 15 )
= 5+(5+( 10 ))
= 5+(5+(5+( 5 )))
13
6.100L Lecture 15
MULTIPLICATION –
RECURSIVE and BASE STEPS
Recursive step a*b = a + a + a + a + … + a
• Decide how to reduce
problem to a
simpler/smaller version = a + a + a + a + … + a
of same problem, plus
simple operations
= a + a * (b-1)
14
6.100L Lecture 15
MULTIPLICATION –
RECURSIVE and BASE STEPS
Recursive step a*b = a + a + a + a + … + a
• Decide how to reduce
problem to a
simpler/smaller version = a + a + a + a + … + a
of same problem, plus
simple operations
= a + a * (b-1)
Base case
• Keep reducing problem
until reach a simple case
that can be solved
directly
• When b=1, a*b=a
15
6.100L Lecture 15
MULTIPLICATION – RECURSIVE
CODE Python Tutor LINK
Recursive step
• If b != 1, a*b = a + a*(b-1)
Base case
• If b = 1, a*b = a
def mult_recur(a, b):
if b == 1:
return a
else:
return a + mult_recur(a, b-1)
16
6.100L Lecture 15
REAL LIFE EXAMPLE
Student requests a regrade: ONLY ONE function call
Iterative:
Student asks the prof then the TA then the LA then the grader
one-by-one until one or more regrade the exam/parts
Student iterates through everyone and keeps track of the new score
Meme girl © source unknown. Woman image ©
2007 NBC Universal. Willy Wonka © 1971 Warner
Bros. Entertainment Inc. Still from Bridesmaids ©
2011 Universal Studios. Still from Cocoon © 2011
Universal Studios. All rights reserved. This
content is excluded from our Creative Commons
license. For more information, see https://
ocw.mit.edu/help/faq-fair-use/
17
6.100L Lecture 15
REAL LIFE EXAMPLE
Student requests a regrade: MANY function calls
Here
you go
Recursive:
1) Student request(a function call to
regrade!): Here
Asks the prof to regrade you go
Regrade
Prof asks a TA to regrade
please?
TA asks an LA to regrade
LA asks a grader to regrade Here
you go
2) Relay the results (functions return Regrade
results to their callers): please?
Grader tells the grade to the LA
Here
LA tells the grade to the TA
you go
TA tells the grade to the prof Regrade
Prof tells the grade to the student please?
Meme girl © source unknown. Woman image © 2007 NBC Universal. Willy Wonka
© 1971 Warner Bros. Entertainment Inc. Still from Bridesmaids © 2011 Universal
Studios. Still from Cocoon © 2011 Universal Studios. All rights reserved. This 18
content is excluded from our Creative Commons license. For more information,
see https://ocw.mit.edu/help/faq-fair-use/ 6.100L Lecture 15
BIG IDEA
“Earlier” function calls
are waiting on results
before completing.
19
6.100L Lecture 15
WHAT IS RECURSION?
Algorithmically: a way to design solutions to problems by
divide-and-conquer or decrease-and-conquer
Reduce a problem to simpler versions of the same problem or to
problem that can be solved directly
Semantically: a programming technique where a function
calls itself
In programming, goal is to
NOT have infinite recursion
Must have 1 or more base cases
that are easy to solve directly
Must solve the same problem on
some other input with the goal of
simplifying the larger input
problem, ending at base case
20
6.100L Lecture 15
YOU TRY IT!
Complete the function that calculates np for variables n and p
def power_recur(n, p):
if _______:
return ______
elif _______:
return ______
else:
return _________________
21
6.100L Lecture 15
FACTORIAL
n! = n*(n-1)*(n-2)*(n-3)* … * 1
For what n do we know the factorial?
n=1 if n == 1:
return 1
How to reduce problem? Rewrite in terms of something simpler
to reach base case
n*(n-1)! else:
return n*fact(n-1)
22
6.100L Lecture 15
RECURSIVE def fact(n):
if n == 1:
FUNCTION return 1
else:
SCOPE return n*fact(n-1)
EXAMPLE print(fact(4))
Global scope fact scope fact scope fact scope fact scope
(call w/ n=4) (call w/ n=3) (call w/ n=2) (call w/ n=1)
fact Some n n n n
4 3 2 1
code
23
6.100L Lecture 15
BIG IDEA
In recursion, each
function call is
completely separate.
Separate scope/environments.
Separate variable names.
Fully I-N-D-E-P-E-N-D-E-N-T
24
6.100L Lecture 15
SOME OBSERVATIONS
Python Tutor LINK for factorial
Each recursive call to a function
creates its own scope/environment
Bindings of variables in a scope are
not changed by recursive call to
same function
Values of variable binding shadow
bindings in other frames
Flow of control passes back to
previous scope once function call
returns value
25
6.100L Lecture 15
ITERATION vs. RECURSION
def factorial_iter(n): def fact_recur(n):
prod = 1 if n == 1:
for i in range(1,n+1): return 1
prod *= i
else:
return prod
return n*fact_recur(n-1)
Recursion may be efficient from programmer POV
Recursion may not be efficient from computer POV
26
6.100L Lecture 15
WHEN to USE RECURSION?
SO FAR WE SAW VERY SIMPLE CODE
Multiplication of two numbers did not need a recursive
function, did not even need an iterative function!
Factorial was a little more intuitive to implement with recursion
We translated a mathematical equation that told us the structure
MOST problems do not need recursion to solve them
If iteration is more intuitive for you then solve them using loops!
SOME problems yield far
simpler code using recursion
Searching a file system
for a specific file
Evaluating mathematical
expressions that use parens
for order of ops
27
6.100L Lecture 15
SUMMARY
Recursion is a
Programming method
Way to divide and conquer
A function calls itself
A problem is broken down into a base case and a recursive step
A base case
Something you know
You’ll eventually reach this case (if not, you have infinite recursion)
A recursive step
The same problem
Just slightly different in a way that will eventually reach the base case
28
6.100L Lecture 15
MITOpenCourseWare
https://ocw.mit.edu
6.100L Introduction to Computer Science and Programming Using Python
Fall 2022
For information about citing these materials or our Terms ofUse,visit: https://ocw.mit.edu/terms.
29
