Lecture_21_Iteration
Iteration
and
Recursion
CSCI 3136: Principles of Programming Languages
Agenda
• Announcements
• Lectures are being recorded
• Assignment 9 is due Monday, July 19
• Test 3, 9:00am, Thursday, July 29
• Student Rating Instruction is open
• Readings: Read Chapter 6.5 – 6.6
• Lecture Contents
• Motivation
• Logical vs Enumeration Loops
• Generators and Iterators
• Recursion
• Tail Recursion
2021-07-12 11:01 AM 2
Keywords
• Iteration
• Loop
• Logically-controlled loops
• Boolean condition
• Pre-loop test
• Post-loop test
• Mid-loop test
• Break statement
• while-loop
• Enumeration-controlled loop
• Index variable
• Step
• for-loop
• Generator
• Self-contained function
• Yield
• Closures
• Local state
• Iterator
• Object
• Sequential access
• Tail Recursion
• Recursion
• Naive recursion
• Helper function
• Multi-way recursion
2021-07-12 11:01 AM 3
End of this Part
CSCI 3136
2021-07-12 11:01 AM 4
Motivation
CSCI 3136
2021-07-12 11:01 AM 5
Motivation
• To be useful, programs need to
• Repeat sequences of instructions
• Decide at run-time how many iterations to perform
• E.g.,
• Process arrays
• Walk lists
• Read arbitrary sized input
• etc
• There are two approaches
• Iteration
• Recursion
• Iteration uses a loop construct that
• Performs all repetitions in the same scope
• Uses side-effects to determine when to stop
2021-07-12 11:01 AM 6
Iteration (Looping)
• Two types of loops
• Logically controlled loops
• Example: while-loop
• Executed until a Boolean condition changes
• The number of iterations is not known in advance
• Enumeration-controlled loops
• Example: for-loop
• One iteration per element in a finite set
• The number of iterations is known in advance
• Some languages do not have loop constructs
E.g., Scheme, which uses tail recursion instead
2021-07-12 11:01 AM 7
Logically Controlled Loops
• Pre-loop test
while (condition) do
…
end
• The loop may be executed 0 or
more times
• Test occurs before the
iteration
• Post-loop test :
do
…
while ( condition )
• Loop is executed at least once
• Test is performed at end of
iteration
• Mid-loop test or one-and-a-
half loop
loop
…
if (condition) break
…
if (condition) break
…
end
• Conditions are tested inside
the loop and may break out
• Modern languages provide a
break statement to use first
two loop constructs in this
way
2021-07-12 11:01 AM 8
Enumeration Controlled Loops
• Use an index variable to count up or down the
number of iterations
• The index variable can be incremented /
decremented by a step other than 1
FOR i = start TO end BY step DO:
…
END
• This loop
• Initializes i to start
• Adds step to i at the end of each iteration
• Tests if i is less than end
• If so, performs another iterations
2021-07-12 11:01 AM 9
Trade-Offs
• Logically controlled loops are very flexible but expensive.
• May have arbitrarily expensive condition
• Cannot be unrolled
• May have arbitrarily expensive step
• Enumeration-Controlled loops
• Have a single int or float comparison
• Can be unrolled to improve pipelining
• Have a simple step,
e.g., increment / decrement
• for-loop in C/C++/Java is syntactic sugar for init-test-step
idiom of logic-controlled while loops.
2021-07-12 11:01 AM 10
init;
while (condition) {
…
increment;
}
for (init; condition; increment) {
…
}
End of this Part
CSCI 3136
2021-07-12 11:01 AM 11
Generators
CSCI 3136
2021-07-12 11:01 AM 12
Iterators and Generators
• Observation: Often, loops are used to iterate
over sequences of elements that are
• Stored in a data structure
• Generated by a procedure
• Read from a file (or input)
• Iterators are a clean way for iterating over a
stored sequence
• Generators are a clean way for generating a
sequence as needed
2021-07-12 11:01 AM 13
Generators
• Idea:
• A generator is a self-contained function that stores its
local state
Sound familiar?
• Instead of returning a value, it yields a value
• Next time it is called, it continues from the yield statement
• Generators provide an easy way for the programmer to
generate a sequence of values
• In languages that do not have generators, a loop is needed to
generate all values at once
• Generators generate the next value and “yield” it when they
are called
• The values are generated only when they are need it
2021-07-12 11:01 AM 14
Generators in Python
• In Python, a generator function returns a generator object
• The generator object has a next() operation, which executes
the code in the generator function “yields” the next value
• Example
def make_counter():
for i in range(0, 1000000):
yield i
cnta = make_counter()
print(next(cnta))
print(next(cnta))
print(next(cnta))
…
• Prints out, 0 1 2 3 …
2021-07-12 11:01 AM 15
A C Implementation of a Counter
int counter() {
static int i = -1;
i = (i + 1) % 1000000;
return i
}
// Idea: state of generator is
// stored in a static variable
// Only one instance possible
2021-07-12 11:01 AM 16
Another Generator in Python
def make_iterator(lst):
for e in lst:
yield e
for item in make_iterator(lst):
print(item)
• Calling this function on a list will return an iterator
that iterates over the list
2021-07-12 11:01 AM 17
A Generator in Scheme
• We have already seen generators in Scheme
• The counter is a generator
(define new-counter (lambda ()
(let ((count 0))
(lambda ()
(set! count (+ count 1))
count
)
)
)
)
This function returns a function that
generates a sequence of numbers 1, 2, …
> (define cnta (new-counter))
> (cnta)
1
> (cnta)
2
> (cnta)
3
>
2021-07-12 11:01 AM 18
End of this Part
CSCI 3136
2021-07-12 11:01 AM 19
Iterators
CSCI 3136
2021-07-12 11:01 AM 20
Iterators
• An iterator is an object that has a next() operation,
which returns the next item in a sequence
• All generators are iterators, but not all iterators are
generators
• Generators are typically a single function that store all
the necessary state to generate the next item
• Iterators do not necessarily keep local state (most
usually do)
• Iterators are typically applied to collections, such as
lists, array, sets, maps, etc
• The iterators are used to sequentially access all items in
a collection
2021-07-12 11:01 AM 21
Iterator Interface
• Idea: Many languages define standard interfaces for iterating over
a data structure
• begin() : returns the first element of the iteration
• next() : returns the next element of the iteration
• end() : returns the last element of the iteration
• Example: C++
for( cont::iterator i = cont.begin(); // get iter
i != cont.end(); // done?
i++ ) { // goto next
cout << *i; // Use i
}
• C++ overloads two operators on the iterators
• ++ : which is the same as calling next()
• * : dereference used to access the value at current locations
2021-07-12 11:01 AM 22
Iterator Interface (in Java)
• Assume that variable coll refers to a Collection of MyObjs
• Before Java 5, iterators were not built-in
Enumeration e = coll.elements(); // get iter
while (e.hasMoreElements()) { // done?
MyObj o = (MyObj) e.nextElement(); // Use o
// Use o
}
• Most modern languages have iterators built-in
• In Java 5 and later:
for (MyObj o : coll) {
// Use o
}
2021-07-12 11:01 AM 23
Iterator Interface (in Python)
• In Python, all loops use iterators
• To implement a simple counting loop you need to create an
iterator
for i in range(0,10):
print(i)
• The range() function returns an integer iterator from 0 to 9
• All collections in Python have iterators
• It’s actually hard to use a collection in Python without iterators
• Even input and output is done using iterators:
• Example: the first line of a scheme parser creates a token iterator
tokens = iter(sys.stdin.read().split())
2021-07-12 11:01 AM 24
Iteration in Functional Languages
• Use closures to create generators and iterators
• Use recursion to iterate over any collection or
sequence
2021-07-12 11:01 AM 25
End of this Part
CSCI 3136
2021-07-12 11:01 AM 26
Tail Recursion
CSCI 3136
2021-07-12 11:01 AM 27
Recursion: It Throws Us for a Loop
• Every iterative procedure can easily be turned into a recursive one:
• The converse is not true
e.g., quicksort, merge sort, fast matrix multiplication, etc.
• Q: Why don’t functional languages support iteration?
• A: Iteration relies on updating the iterator variable (side effect)
Iterative Recursive
while (condition) {
S1;
S2;
...
}
procedure P() {
if (condition) {
S1;
S2;
...;
P();
}
}
2021-07-12 11:01 AM 28
Tail Recursion
• Naive recursion is less efficient than tail iteration
• Every recursive call uses stack space
• For long recursions, it is possible to run out of stack
space
• An optimizing compiler often converts recursion
into iteration when tail recursion occurs
• Tail recursion occurs when there is no work done
after the recursive call
• This is a standard approach for implementing
iteration in functional languages
2021-07-12 11:01 AM 29
Example 1:
• What does this do?
(define sum
(lambda (int_list)
(if (null? int_list)
0
(+ (car int_list)
(sum (cdr int_list)))))
• Is this tail recursive?
• Why not?
• Non-tail-recursive implementations can be made tail
recursive
• Idea: Work to be done after the recursive call is passed
to the recursive call.
• A Helper function is typically used
Is list
empty?
Yes,
return 0
Recursive
case
Addition after the
recursive call
2021-07-12 11:01 AM 30
Example 1: Tail Recursive Version
• Here is a tail recursive version
(define sum_helper
(lambda (total int_list)
(if (null? int_list)
total
(sum_helper
(+ total (car int_list))
(cdr int_list)))))
(define sum
(lambda (int_list)
(sum_helper 0 int_list)))
Pass the running
total and the
rest of the list
If list is empty,
return total
Recursive
case
Increment
total first
Remainder
of the list
Call sum_helper,
initial total is 02021-07-12 11:01 AM 31
End of this Part
CSCI 3136
2021-07-12 11:01 AM 32
Tail Recursion Example 2
CSCI 3136
2021-07-12 11:01 AM 33
Example 2: Sum of f(i)
• This is not a tail recursive version, why?
(define sum_f
(lambda (f low high)
(if (= low high)
(f low)
(+ (f low)
(sum_f f (+ low 1) high)
)
)
)
)
• Can we do better?
2021-07-12 11:01 AM 34
Example 2: Tail Recursive Version
• What is happening here?
(define sum_f (lambda (f low high)
(letrec ((sum (lambda (i total)
(if (> i high)
total
(sum (+ i 1) (+ total (f i)))
) )
(sum low 0)
)
)
• Where is our sum_helper?
Need
letrec J
Increment
total
Increment
i
Call
helper2021-07-12 11:01 AM 35
End of this Part
CSCI 3136
2021-07-12 11:01 AM 36
Tail Recursion Example 3
CSCI 3136
2021-07-12 11:01 AM 37
Example 3: Fibonacci
• What’s happening here?
(define fib (lambda (n)
(if (< n 2)
n
(+ (fib (- n 1))
(fib (- n 2))
)
) )
)
• Why is this not tail recursive?
• Can we do better?
2021-07-12 11:01 AM 38
Example 3: Tail Recursive
• What’s happening here?
(define fib (lambda (n)
(letrec ((fib (lambda (f1 f2 i)
(if (= i n)
f1
(fib f2 (+ f1 f2) (+ i 1))
))))
(fib 0 1 0)
)
)
2021-07-12 11:01 AM 39
Is Tail Recursion Always Possible?
• It depends…
• Answer 1:
• Every recursive algorithm can be implemented
iteratively by using a stack
• Every iterative algorithm can be implemented using tail
recursion
• So, technically, every recursive algorithm has a tail-
recursive variant.
• Answer 2:
• In practice, multi-way recursive algorithms cannot be
implemented in a tail-recursive manner that is also
intuitive.
2021-07-12 11:01 AM 40
End of this Part
CSCI 3136
2021-07-12 11:01 AM 41