CS计算机代考程序代写 scheme python data structure c/c++ compiler Java flex c++ algorithm Lecture_21_Iteration

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