Slides

S1: Overview of Chapter 2.1-2.2

Topics:
- 2.1 Recursive Procedures
  - 2.1.1 Droid Model - tracing procedure calls
  - 2.1.2 Recursive definitions for repetition
- 2.2 Designing Recursive procedures
  - 2.2.1 Base and Recursive Cases
  - 2.2.2 Linear and Multiway Recursion
- Reading:
- Chapter 2.1, 2.2
- Recommended Ex.: 1,6,8,11,14

S2: 2.1 Procedure Calls = Droids

Evaluation models help us read, understand, debug procedures
Droid
- is a call/invocation of a USER-defined procedure
- Has incoming arguments, and returning result
- Life-cycle:
  - (i) Bind actual argments to corresponding formal arguments
  - (ii) Evaluate the body of the procedure using The Rules (1.5)
  - (iii) Return results to the caller
- Example (fig. 2-2, pp 60): Consider function f and g
  (define f (lambda (x) (- (g (add1 x)) 5 ) ) ) )
  (define g (lambda (y) (* y 2) ) )
- Q? How many droid will the call (f 3) generate?
- Q? Identify the bindings, callers of each droid?

S3: Droid Model (2.1.1)

Droid Model = an execution state at procedure call level
Components
- One droid per procedure call
- Parameter values
- Caller - callee relationship
Diagram for droid models
- Droid = a box with procedure name inside
- Caller info. = arrow from caller to callee
- Parameter = value on arrow
Droid Model Vs. Execution trace
- Execution trace = a sequence of droid models,
  - One for each time instant
- Droid model = an execution state at a time instant
Q? How to trace a scheme program at function call level?

S4: Droid Model (2.1.1) Vs. The Rules model (1.5)

The Rules (Section 1.5) can provide more details at form-level
(define f (lambda (x) (- (g (add1 x)) 5 ) ) ) )
(define g (lambda (y) (* y 2) ) )
Evaluation of (foo 3) ;;; application
( (lambda (x) (- (g (add1 x)) 5 ) ) ) 3) ;;; procedure
( - (g (add1 3)) 5 ) ;;; application
(#{minus} (g (add1 3)) 5 ) ;;; application
(#{minus} ( (lambda(y) (* y 2)) (add1 3)) 5);; application
(#{minus} ( (lambda(y) (* y 2)) (#{add1} 3)) 5);; primitive
(#{minus} ( (lambda(y) (* y 2)) 4) 5) ;;; procedure
(#{minus} (* 4 2) 5 ) ;;; procedure
(#{minus} (#{times} 4 2) 5 ) ;;; primitive
(#{minus} 8 5) ;;; primitive
3
Droid model Vs. The Rules
Droid model has less details
Debugging Larger scheme-program
1. Use droid model to narrow down bug to a procedure
2. Use The Rules (1.5) to analyze forms within that procedure

S5: Repetition Via Recursive Definitions

Repetitions - Examples
- Compute the sum of integers from 1 thru' 10
- Compute the product of integers from 1 thru' N
- Apply The Rules (1.5) till the form reduces to a primitive form
Specifying repetition in a computer program
- (i) Create new special form - Language C has for, while, do, ...
- (ii) Use procedure - recursive definition
  (define interpreter
  (lambda ()
  (print-out (evaluate (read-a-scheme-form) ) )
  (interpreter) ;;; Repetition via recursive call
  )
Repetition in Scheme (3316)
Use recursive procedures
Focus on numeric functions in chapter 2
Work with functions on lists, trees in chapter 4

S6: Understanding Recursive Function

factorial(n) = product of positive numbers from 1 to N
- or factorial(n) = n * factorial(n - 1)
  (define factorial
  (lambda(n)
  (if (= n 0)
  1
  (* n (factorial (sub1 n) ) )
  )))
Ex. Draw a droid model of invocation (factorial 5)
Trace at procedure-call level
(factorial 5)
(* 5 (factorial 4))
(* 5 (* 4 (factorial 3)))
(* 5 (* 4 (* 3 (factorial 2))))
(* 5 (* 4 (* 3 (* 2 (factorial 1)))))
(* 5 (* 4 (* 3 (* 2 (* 1 (factorial 0))))) )
(* 5 (* 4 (* 3 (* 2 (* 1 1 )))))
...

S7: Structure of a Recursive Definitions

Recursive definition have
- (i) Base Steps - answers are known
- (ii) Recursive Steps - calls itself with a subproblem
- (iii) Sequence of recursive calls should lead to base case
  - Repetition ends when base case is reached
- Ex. Identify the structure of factorial function.
- What are the base and recursive cases?
- Do recursive calls in factorial lead to base case?
Ex. Evaluate (factorial -3) using droid model
- Q? How many droids will there be?
  (factorial -3)
  (* -3 (factorial -4))
  (* -3 (* -4 (factorial -5)))
  (* -3 (* -4 (* -5 (factorial -6))))
  ...
Issue of infinite repetition
Is infinite loop always undesirable ?
Q? Redefine factorial to eliminate the infinite loop.

S8: Designing Recursive Definitions

Strategy:
- 0. Identify function parameters, e.g. f(N)
- 1. Identify recursive case(s)
  - e.g. Q? Can f be computed from subproblems,
  - e.g. f(N) from f(N-1), f(N/2), etc.?
  - e.g. f(M,N) from f(M,N-1), f(M/2,N), etc.?
- 2. Identify base case(s)
  - Q? Is f well-known for some cases, e.g. N = 0 or N = 1.
- 3. Termination: recursive calls should lead to a base case
Ex. Identify Base and Recursive Cases for following functions
- f(N) = sum of positive-integers from 1 to N
- g(N) = sum of squares of positive numbers from 1 to N
- h(N) = sum of positive powers of 2.
- s(M,N) = sum of positive-integers from M to N
- s(scheme-form) = evaluation of the scheme form
  - using The Rules in 1.5

S9: Recursive function with >1 arguments

Ex. lander (pp 69)
Ex. cube-root-solve (pp 73)
Problem: Given N find cube-root(N). Assume N > 1.
Algorithm: Binary search in interval 1 ... N.
- 1. Initialize x0 be 1 and x1 be N
- 2. Let current interval be x0 ... x1
- 3. Midpoint xM = (x0 + x1)/2
- 4. If cube(xM) > N then search x0 ... xM
  - else search xM ... x1
- Algorithm works as cube(x)is a monotonic function
- Example Execution for cube-root(3)
  try 1..3, xM= 2, cube(xM) > 3 = > try 1..2
  try 1..2, xM= 1.5, cube(xM) > 3 = > try 1..1.5
  try 1..1.5, xM= 1.25, cube(xM) < 3 = > try 1.25..1.5
  try 1.25..1.5, xM= 1.375, cube(xM) < 3 = > try 1.375..1.5
  try 1.375..1.5, xM= 1.4375, cube(xM) < 3 = > try 1.4375..1.5
  ...

S10: Cube-root - continued

Developing a recursive formulation
- 0. Identify functions and parameters
- 1. Identify recursive case(s)
- 2. Identify base case(s)
- 3. Termination: recursive calls should lead to a base case
Function formulation -
- cube-root(a) returns the solution
- cube-root-solve(a x0 x1) recurses to find solution
- Helper functions: midpoint(x1 x2), cube(x)

S11: Cube-root - continued

Base Case for cube-root-solve(a x0 x1)
- (x0 = x1) = > cube-root(a) = x0 = x1.
- But, cube-root(a) may be irrational,
  - which can not be represented in computers!
- We should be happy with approximate solutions,
  - i.e. (x1 - x0) < epsilon
- Recursive Cases: (x1 -x0) > epsilon
  (define (cube-root-solve a x0 x1)
  (if ( < (- x1 x0) epsilon)
  (mid-point x0 x1)
  (if ( > (cube (mid-point x0 x1)) a)
  (cube-root-solve a x0 (mid-point x0 x1))
  (cube-root-solve a (mid-point x0 x1) x1))))
  (define (cube-root a) (cube-root-solve a 1 a))
  (define (mid-point p q) (/ (+ p q) 2)
  (define epsilon 0.0001 )

S12: Multi-way Recursion

What is multi-way recursion?
- Some problem use > = two subproblems to get solved
- e.g. f(N) = h ( f(N-1), f(N-2), f(N-3) )
- Series: 1, 1, 2, 3, 5, 8, 13, ...
Examples
- Ex. flushes (pp 77), store (pp. 79)
- Fibonacci, Ackerman
- Combinations, Arrangements, ...
Q? Why is multi-way recursion interesting?
- Common in computer science, e.g. process trees (Ch. 4)
  - Algorithm design technique
- Illustrates computational complexity (Ch. 2.2)
  - Quadratic, Exponential

S13: Multi-way Recursion: Fibonacci numbers

Example: Series of fibonacci number
- 1, 1, 2, 3, 5, 8, 13, 21, 34,
- Used to model population growth
- Yield efficient data-structure (heap)
Exercise
- Q? Determine next three number in this series.
- Q? Write an equation for computing fib(i)
  - using fib(i-1), fib(i-2), fib(i-3), ...
- Q? Write a recursive function to compute fib(i).
  - Base Cases
  - Recursive Cases
    ;;;;;;;;;;;;;;;
    (define (fib n)
    (if ( < = n 1)
    1
    (+ (fib (- n 1)) (fib (- n 2)) )
    ))

S14: Multi-way Recursion: Ackerman Function

Ackerman function
(define (Ackerman n m)
(if (= n 0)
(add1 m)
(if (= m 0)
(Ackerman (sub1 n) 1)
(+ (Ackerman n (sub1 m)) (Ackerman n (sub1 m)) ))));;;
Ex. Compute the values of the following :
(Ackerman 1 0), (Ackerman 0 1)
(Ackerman 2 2)
(Ackerman 3 3)
(Ackerman 4 3) can take a lot of work!
2, 3, 7, ...

S15: Overview of Chapter 2.3-2.4

Administrative
- Class Performance on Quiz:
  - Median = 13/20, 20th percentile = 10
  - adequate foundation of Calculus I
- Topics:
- 2.3 Measuring the Cost of a Computation
  - 2.3.1 Time Complexity - big-O notation
  - 2.3.2 Space Complexity, Tail Recursion
- 2.4 Designing, Testing and Debugging
Reading:
- Chapter 2.3, 2.4
- Recommended Ex.: 15..18,20,22,23

S16: 2.3 Measuring the Cost of a Computation

Why measure the computation cost?
- Some algorithms take too long
  - e.g. exhaustive enumeration
  - Time for Chess Moves > life of universe
- Some problems should have no fast algorithms
  - e.g. encryption, secure code
- Some problems have multiple algorithms
  - We what to choose the "best" algorithm!
  - e.g. fibonacci- multi-way recursion, tail-recursion
- Cost Components
- Time complexity = time to execute a program with an input
- Space complexity = memory size needed for an input
- Other costs = $$$ for coding, testing, maintenance,...

S17: 2.3.1 Big-Oh notation

Cost model = a function/formula
- to determine cost given problem size
- e.g. cost(factorial, problem-size = n) = An + B
Comparing function asymptotically
- f(n) = O( g(n) ) if and only if
  - Limit {n - > infinity; f(n) / g(n) = constant }
  - and Limit {n - > infinity; g(n) / f(n) = constant }
- Ex. Which of the following functions are O( n ):
- f0(n) = 10000
- f1(n) = log(n)
- f2(n) = 1000 n + 200
- f3(n) = n + sqrt(n) + cube-root(n)
- f4(n) = n + sqr(n)
- f5(n) = 1 + 2 + 3 + 4 + ... + n
- f6(n) = 1 * 2 * 3 * ... * n

S18: 2.3.1 Time Complexity

Time complexity = time to execute a program with an input
- In Droid model, count of droids
- In Rules model, count of rewritings
Issue in cost model TC(..) for time
- = TC( problem size, computer hardware, O.S., language, ...)
- TC may be a discrete (i.e. discontinuous)
- TC may be piece-wise defined
Big-Oh cost model for time-complexity
- TC(N) = O ( f(n) ), where
  - f(n) = c, or log(n), n, sqr(n), cube(n), ...
- Ex. TC(N) = O( log(N )

S19: 2.3.1 Time Complexity

Observations on the Big-Oh model for time-complexity
- Only one variable = N = problem size
- Simplified, ignores smaller terms, constants
  - TC1(N) = 17*sqr(N) + 10 N + 20 = O ( sqr(N) )
  - TC2(N) = sqr(N) + 10000 N = O ( sqr(N) )
- Asymptotic behaviour as N - > large values
Notes on Big-Oh model
- Not to compare TC1(N) and TC2(N) for small N
- O( cube(N) ) is fairly complex, consider N = 1 million
- O( exponential(N) ) is a killer !
  - NP-completeness Box
  - Book: What Computers Can Not Do? - Dreyfus

S20: 2.3.2 Space Complexity, Tail Recursion

Space complexity = memory size needed for an input
- How does memory usage grow with problem size?
Why do we need memory?
- Store the code of the program
- Store droids, and their arguments, etc.
- Data structures, e.g. lists, trees
Big-Oh cost model for space-complexity SC(N)
- SC(N) = O ( f(n) ), where
  - f(n) = c, or log(n), n, sqr(n), cube(n), ...
- Notes on Big-Oh model for space complexity
- Only accounts for variable costs, not fixed cost
  - e.g. number of droids in factorial(N)
- Not useful for small N

S21: Space Complexity

Ex. SC(N) for factorial,
(define (f N)
(if (= n 0)
1
(* n (factorial (sub1 n) ) ) )))
Trace at procedure-call level
(factorial 5)
(* 5 (factorial 4))
(* 5 (* 4 (factorial 3)))
(* 5 (* 4 (* 3 (factorial 2))))
(* 5 (* 4 (* 3 (* 2 (factorial 1)))))
(* 5 (* 4 (* 3 (* 2 (* 1 (factorial 0))))) )
(* 5 (* 4 (* 3 (* 2 (* 1 1 )))))
...
Q? How many droids needed for factorial(N) ?
SC( factorial(N) ) = O( N )
Since maximum number of droids = O( N )

S22: 2.3.2 Reducing Memory Use => Tail Recursion

Tail recursion achieves same effect in Scheme
- recursion step is absolutely the last step in procedure
- recursive step is not part of another expression
- Droid for procedure can be reused for the recursive call
  - to save memory overheads
- Ex. Which of the following functions are tail-recursive?
- factorial
- cube-root-solve
- fibonacci
- Ackerman

S23: Test for Tail Recursion: Examine trace

Trace of cube-root-solve
(cube-root 3)
(cube-root-solve 3 1 3)
(cube-root-solve 3 1 2)
(cube-root-solve 3 1 1.5)
(cube-root-solve 3 1.25 1.5)
(cube-root-solve 3 1.375 1.5)
(cube-root-solve 3 1.4375 1.5)
Compare trace of cube-root-solve with trace of factorial
recursive call is the last step
droid can be reused
cube-root-solve is tail-recursive
Recall the definitions
(define (cube-root-solve a x0 x1)
(if ( < (- x1 x0) epsilon)
(mid-point x0 x1)
(if ( > (cube (mid-point x0 x1)) a)
(cube-root-solve a x0 (mid-point x0 x1))
(cube-root-solve a (mid-point x0 x1) x1))))
(define (cube-root a) (cube-root-solve a 1 a))
(define (mid-point p q) (/ (+ p q) 2)
(define epsilon 0.0001 )

S24: 2.3.2 Converting Recursion to Tail-Recursion

Remarks of a C programmer on factorial function
- Use iteration: Save space for droids in recursion
  /* code-fragment to compute factorial(N) */
  a = 1; count = N;
  while (count > 0) {
  a = a * count;
  count = count - 1;
  }
Tail recursion could do the same in Scheme!
Use accumulator variable, helper functions
Example: tail-recursive factorial
(define (fact2 n) (fact2-helper n 1) )
(define (fact2-helper n a)
(if (= n 0)
a
(fact2-helper (- n 1) (* n a) ) ) )

S25: 2.3.2 Recursion Vs. Tail-Recursion

Tail-recursive solution space memory
- Droids for previous recursive calls can be reused
  - since it has nothing more to do later!
    ; trace for (fact2 5)
    (fact2-helper 5 1)
    (fact2-helper 4 5)
    (fact2-helper 3 20)
    (fact2-helper 2 60)
    (fact2-helper 1 120)
    (fact2-helper 0 120)
- But, Tail-recursive solution is more complex
- Needs a helper procedure, and accumulator parameter
Summary:
Develop simple recursive formulations first.
If memory use is a problem, then
explore tail recursive formulation, whenever possible

S26: 2.4 Testing Recursive Procedures

Checking Correctness
- Mathematical Proofs - (Ch. 10)
- Testing -
  - give input; match actual output with expected output.
  - Issue: How many testcases to use?
- Criteria for Choosing testcases:
- Black-box : Do not look at the code
  - Use problem statement to cover boundary cases,
  - various partitions of the domain, etc.
  - Ex. factorial n = 5 (domain), 2.3, -1 (out of domain)
- Glass-box : Look at the code
  - Choose testcase to cover statements, conditions
  - Ex. factorial: n = 0, n = 5 will try both sides of "if"
- Recall definition for factorial,
  (define (f N)
  (if (= n 0)
  1
  (* n (factorial (sub1 n) ) ) )))

S27: 2.4 Debugging Recursive Procedures

If Testing reveals presence of an error
- Debugging follows using a trace
- Common Errors
- 1. Infinite recursion
- 2. Recursing one step too many times
- 3. Recursing one step too few times
What to check?
- Condition separating base case and recursive cases
- Base case - missing one?, extra one?, too specific?
- Recursive call - parameter passing

S28: 2.4 Debugging Recursive Procedures

Function sum-from-1-to-N need to compute the sum 1 + 2 + ... + N
- e.g. sum-from-1-to-N( 4 ) = 1 + 2 + 3 = 6
- e.g. sum-from-1-to-N( 5 ) = 1 + 2 + 3 + 4 + 5 = 15
- Ex. Use tracing to analyze following functions with input 3.
- (i) Find the function correctly implementing sum-from-1-to-N.
- (ii) Describe the errors in other definitions:
- (iii) Convert the correct one to tail-recursive formulation
  (define (f1 N)
  (if ( > N 1)
  (+ N (f1 (- N 1)) ) ))
  
  (define (f2 N)
  (if ( > N 1)
  (+ N (f2 (- N 1)) )
  0 ))
  
  (define (f3 N)
  (if (= N 1)
  1
  (+ N (f3 (+ N 1)) ) ))
  
  (define (f4 N)
  (if ( > N 1)
  (+ N (f4 (- N 1)) )
  N ))
  
  (define (f5 N)
  (if ( < N 1)
  (f4 (+ N (- N 1)) ) ))