SICP的Python实现/SICP的Python实现1.2

Procedures and the Processes They Generate

1. Linear Recursion and Iteration

1. (define (factorial n)
     (if (= n 1)
         1
         (* n (factorial (- n 1)))))

      1 factorial = lambda n: 1 if n==1 else n*factorial(n-1)
   

2. (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)))

      1 fatorial = lambda n: fact_iter(1, 1, n)
      2 fact_iter = lambda product, counter, max_count: product if counter > max_count else fact_iter(counter*product, counter +1, max_count)
   

2. Tree Recursion

1. (define (fib n)
     (cond ((= n 0) 0)
           ((= n 1) 1)
           (else (+ (fib (- n 1))
                    (fib (- n 2))))))

      1 fib = lambda n: 0 if n==0 else ( 1 if n==1 else fib(n-1)+fib(n-2) )
   

2. (define (fib n)
     (fib-iter 1 0 n))
   
   (define (fib-iter a b count)
     (if (= count 0)
         b
         (fib-iter (+ a b) a (- count 1))))

      1 fib = lambda n: fib_iter(1, 0, n)
      2 fib_iter = lambda a, b, count: b if count ==0 else fib_iter(a+b, a, count-1)
   

3. (define (count-change amount)
     (cc amount 5))
   (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) 5)
           ((= kinds-of-coins 3) 10)
           ((= kinds-of-coins 4) 25)
           ((= kinds-of-coins 5) 50)))

      1 count_change = lambda amount: cc(amount, 5)
      2 cc = lambda amount, kinds_of_coins: 1 if amount==0 else 0 if amount < 0 or kinds_of_coins == 0 else cc(amount, kinds_of_coins-1)+cc(amount-first_denomination(kinds_of_coins), kinds_of_coins)
      3 first_denomination = lambda kinds_of_coins: 1 if kinds_of_coins==1 else 5 if kinds_of_coins==2 else 10 if kinds_of_coins==3 else 25 if kinds_of_coins==4 else 50 if kinds_of_coins==5 else 0
   

4. (count-change 100)
   292

      1 count_change(100)
   

3. Orders of Growth

4. Exponentiation

1. (define (expt b n)
     (if (= n 0)
         1
         (* b (expt b (- n 1)))))