Graduate Program KB

SICP

Chapter 1.2

Linear Recursion and Iteration

  • Linear recursive processes involve a sequence of deferred operations, each step requiring the previous to complete
    • Stack space grows linearly as the number of recursive calls increase
    • Notice in the example, the else case multiples n and the result of a recursive call. The operand * must be stored then applied once the call is computed
(define (factorial n)
    (if (= n 1)
    1
    (* n (factorial (- n 1)))))
  • Linear iterative processes only track a set number of variables, updating them and passing them to the next call
    • Fixed amount of memory
    • product is the current total, counter is the current iteration and max-count informs the algorithm at which iteration to stop
(define (factorial n)
    (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
    (if (> counter max-count)
    product
    (fact-iter (* counter product)
               (+ counter 1)
                max-count)))

Tree Recursion

  • Tree recursive processes involve multiple recursive calls at each step which form branches similar to a tree
    • Since each call can generate many additional branches, the run time can become exponential
    • Notice in Ackermann's function, in the else case, there are two recursive calls which form two branches in the tree at each step
    • This results in an exponential run time of O(2n)
(define (A x y)
    (cond ((= y 0) 0)
          ((= x 0) (* 2 y))
          ((= y 1) 2)
          (else (A (- x 1) (A x (- y 1))))))

Orders of growth

  • Describe time and space requirements of a function based off input size, it provides insight of an algorithm's efficiency and scalability
  • The most common orders of growth include: O(1), O(log n), O(n2), O(2n)

Exponents

  • Raising base to power using a linear process
(define (expt b n)
    (if (= n 0)
    1
    (* b (expt b (- n 1)))))
  • Recursive exponentiation can use a divide and conquer strategy (successive squaring) to reduce the problem size by half with each recursive call
    • Order of growth becomes logarithmic (O(log n))
(define (fast-expt b n)
    (cond ((= n 0) 1)
          ((even? n) (square (fast-expt b (/ n 2))))
          (else (* b (fast-expt b (- n 1))))))

(define (even? n)
    (= (remainder n 2) 0))

  • Example of successive squaring:

    • b2 = b * b
    • b4 = b2 * b2
    • b8 = b4 * b4

  • If the power is odd, then decrement it to an even power and apply a multiplication of the base to the final result

Other

  • In Dr Racket, add to use the in-built procedure current-inexact-milliseconds to calculate runtime
#lang racket/base
  • For iteration, define a helper function which won't affect our signature call
  • Therefore, our program can still work despite a different algorithmic implementation which may require new parameters
  • For example, calculating factorials iteratively requires 3 parameters compared to 1, and two of them have initial values of 1:
; Recursive
(define (factorial n) ( ... ))

; Iterative
(define (factorial n)) (
    (fact-iter 1 1 n)
)

(define (fact-iter product count max-count) ( ... ))