Transcript Recitation 2

‫מבוא מורחב למדעי המחשב‬
‫‪Scheme‬בשפת‬
‫תרגול ‪2‬‬
Outline
• Scoping and block structure
• Recursive and iterative processes
• Orders of growth
2
Scoping
•
We have seen two methods to introduce names into a program:
– Define form introduces a name associated with a procedure or
an expression:
(define x 5)
(define (f x) (* x x))
– Lambda expression introduces names for formal parameters
(define (g a b) (+ a b))
((lambda(a b) (+ a b)) 2 3)
• Need rules to interpret names.
(define x 5)
((lambda(x)(+ x 1)) x)
3
Reminder: Bounded variables
• A procedure definition binds its formal
parameters (their names)
• These names are called bounded variables.
• Other variables are free variables
(define y 7)
(define (foo x) (+ x y))
x is bounded to foo, while y is free
4
Reminder: Scope
• The set of expressions for which binding defines
a name is called a scope of this name
• A bound variable has its binding function’s body
as a scope, and is unknown outside its scope
• Free variables are known anywhere in the
program
• For variables with the same name and
overlapping scopes, the more internal binding
overrides the other
5
Example
(define y 7)
(define z 5)
(define (foo x z) (+ x z y))
• Foo binds x and z. x and z are bounded to foo
• Scope of x and z is the body of foo
• y is known everywhere, z=5 is only outside foo
• The meaning of foo will not change if we’ll change the
names of its formal parameters.
6
Internal Definitions
• Can define a name inside the lambda expression (local to this
procedure/lambda expression)
• It’s scope is limited to the rest of the body of the procedure
• (define (g x)
(define a 5)
(* x a))
• Note: Body of a procedure(lambda expression) can consist of
multiple sub-expressions.
– The value of the last one is defined to be the value of the procedure
7
Reminder: Block structure
• Binding/Internal definitions isolate a variable
from the rest of the program (limit its scope)
• Can we isolate procedure from the rest of the
program (to limit its scope)?
• Block structure: defining procedures inside other
procedure
8
Example
• (define (f x)
(define (g z) (* z z))
(+ (g x) (g x))
)
• (define (h x)
(define (g x) (+ x x))
(- (g x) (g x)))
)
9
Why do wee need block structure and
scoping?
• It makes our life easier:
– Don’t have to remember which names are
already used
– Hide away helper procedures to see the
overall structure of the program
10
Example 2
(define x 3)
(define (foo y z)
(define (g z x)
(+ x y (* 2 z)))
(g (+ x z) y))
z,x
y,z
(foo x 5)
11
Example 2: Cont’d
(define x 3)
3 5
(define (foo y z)
8 3
(define (g z x)
3 3
8
(+ x y (* 2 z)))
3 5 3
(g (+ x z) y))
z,x
y,z
3
(foo x 5)
22
12
Reminder: Recursive algorithm
• Reduce problem to one or more sub-problems of
smaller sizes (linear or tree recursion) and solve
them recursively
• Solve the very small sized problems directly
• Usually some computations are required in order
to split problem into sub-problems or /and to
combine the results
13
Example 1
• Compute f(n)=n!
• Notice that f(n)=n*f(n-1) if n>1 and f(1)=1;
• Algorithm:
1. If n=1 return 1
2. Computing factorial for n-1 if n>1
3. Multiply result by n and return
14
Example 2a
• Compute the average of set of n=2^k numbers
– Avg({x1 .. xn})=(x1 +.. +xn)/n
• Notice that:
– Avg({x1 .. xn})=[Avg({x1 .. Xn/2})+Avg({xn/2+1 .. xn})]/2
• Algorithm
1. If input set size is 1, return the input as its average
2. Divide set into 2 subsets of n/2 if n>1
3. Find an average of each subset
4. Return average of two results
15
Example 2b
• Compute the average of set of numbers
– Avg({x1 .. xn})=(x1 +.. xn)/n
• Notice that:
– Avg({x1 .. xn})=[xn + (n-1)*Avg({x1 .. Xn-1})]/n
• Algorithm
1. If input set size is 1, return the input as its average
2. Find average of last n-1 numbers
3. Multiply result by (n-1) add xn and the divide by n
16
Example 3
• Find if the number x is a power of 2
F(x)=#t if x=2^n for some n or #f otherwise
• Notice
– F(x)=F(x/2) if x is even, F(x)=#t if x=1 and #f
otherwise
• Algorithms
1. If x is odd return #f , if x=1 return #t
2. Compute and return for x/2
17
Recursive calls
• Function/procedure that calls to itself
called recursive procedure
• Can’t call to itself every time as have to
stop somewhere
• Recursive algorithms are usually
implemented using recursive calls
18
The conditional form
(cond (<test-1> <consequent-1>)
(<test-2> <consequent-2>)
. . .
(<test-n> <consequent-n>)
(else
<consequent-else>))
(define (abs x)
(cond ((> x 0) x)
((= x 0) 0)
(else (- x))))
19
Scheme Examples
• (define (f n) (if (= n 1) 1 (* n f (- n 1)))))
• (define (is_pow2 x)
(cond (
((= x 1) #t)
((odd? x) #f)
(else (is_pow2 (/ x 2))))
))
20
Special case of recursive processes
• No need to do computations after return of
recursive call
call
call
calc
call
calc
return val
call
return
same val
return
same val
calc
return val
call
no
calc
call
return val
call
no
calc
return
same val
calc
call
no
calc
calc
return val
21
converting a tail recursive call
to an iterative process
call
call
don’t
wait
call
don’t
wait
call
don’t
wait
calc
return val
In Scheme, a tail recursive procedure results
in an iterative process!
22
Different Meanings of Recursions
Recursive Algorithms
Iterative Algorithms
Recursive Scheme Function
Tail Recursion
Recursive Process
Iterative Process
23
Fibonacci Series
Every element is the sum of its predecessors: 1, 1, 2, 3, 5, 8, 13, 21…
Recursive algorithm
fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2) :n > 1
Tree recursion
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))
Iterative algorithm
Initialize: a = 1, b = 0
count = n
Step:
anew = aold + bold
bnew = aold
count = count - 1
Tail Recursion
(define (fib n)
(define (fib-iter a b count)
(if (= count 0) b
(fib-iter (+ a b) a (- count 1))))
(fib-iter 1 0 n))
24
Tree Recursion
25
Implementing loops using tail recursion
• Usually using helper local function (iterator)
• Pass loop local variables as an argument
(usually includes some sort of counter)
• Check stopping condition
• Make initial call with initial state arguments
26
Example(Recursion)
• Input: Amount of money : $1.50
• Output: Number of different ways to
construct the amount using coins of
1,2,5,10,15,20,50 cents
• Assume there is unlimited number of coins
of each value
27
Counting Change
= 2x
= 3x
=
+ 4x
+
+ 93x
28
Counting Change
CC(
,{
CC(
,{
CC(
-
})=
})+
,{
})
29
Counting Change
(define (count-change amount)
(cc amount 6))
(define (cc amount kinds-of-coins)
(cond ((= amount 0) 1 )
((or (< amount 0) (= kinds-of-coins 0)) 0 )
(else (+ (cc amount
(- kinds-of-coins 1) )
(cc (- amount
(first-denomination kinds-of-coins))
kinds-of-coins
)))))
(define (first-denomination kinds-of-coins)
(cond ((= kinds-of-coins 1) 1)
((= kinds-of-coins 2) 2)
((= kinds-of-coins 3) 5)
((= kinds-of-coins 4) 10)
((= kinds-of-coins 5) 20)
((= kinds-of-coins 6) 50))))
30
Greatest Common Divisor
Given integers a>b0
gcd(a,0) = a
gcd(a,b) = gcd(b, a mod b)
By Substitution
(gcd 30 21)
(gcd 21 9)
(gcd 9 3)
(gcd 3 0)
3
(define (gcd a b)
(if (= b 0) a
(gcd b (remainder a b))))
31