SICP学习笔记 1.2.2 树形递归

  练习1.11

   递归过程

 

(define (func n)
  (if (< n 3)
	  n
	  (+
	   (* 1 (func (- n 1)))
	   (* 2 (func (- n 2)))
	   (* 3 (func (- n 3))))))

     

    迭代过程

 

(define (func n)
  (fun-iter 0 1 2 n))
(define (fun-iter a b c count)
  (if (= count 0)
	  a
	  (fun-iter b c (+ (* 1 c) (* 2 b) (* 3 a)) (- count 1))))

 

  练习1.12

 

(define (pasca n i)
  (cond ((= i 1) 1)
		((= i (+ n 1)) 1)
        (else (+ (pasca (- n 1) (- i 1)) (pasca (- n 1) i)))))

 

 

  练习1.13

 

    已知:f(n+1) = f(n) + f(n-1)   (1)

 

    设存在f(n+1) + x*f(n) = y*[f(n) + x*f(n-1)]  (2),则有

    f(n+1) = (y-x)*f(n) + x*y*f(n-1)

    根据(1)，则有y-x=1, x*y=1，则有x*(x+1)=1

    此方程有解

    x=(√5-1)/2、y=(√5+1)/2

    则存在等比数列f'(n),其首项为f(2) + [(√5-1)/2]*f(1) = (√5+1)/2,公比为(√5+1)/2

    则f'(n) = [(√5+1)/2]^n,即

    f(n+1) + [(√5-1)/2]*f(n) = [(√5+1)/2]^n   

    f(n+1) = [(1-√5)/2]*f(n) + [(√5+1)/2]^n     (3)

 

    设存在f(n+1) + x*[(√5+1)/2]^(n+1) = [(1-√5)/2]*[f(n) + x*[(√5+1)/2]^n]   (4),则有

    f(n+1) = [(1-√5)/2]*f(n) + [(√5+1)/2]^n*(-√5*x)

    根据(2),则有

    -√5*x=1,则x=-√5/5

    代入(4),得

    f(n+1) - (√5/5)*[(√5+1)/2]^(n+1) = [(1-√5)/2]*[f(n) - (√5/5)*[(√5+1)/2]^n]

    则存在等比数列f''(n),其首项为f(1)- (√5/5)*[(√5+1)/2] = (5-√5)/10,公比为(1-√5)/2

    则f''(n) = [(5-√5)/10]*[(1-√5)/2]^(n-1)，则

    f(n)- (√5/5)*[(√5+1)/2]^n = -(√5/5)*[(1-√5)/2]^n

    f(n) = (√5/5)*[(√5+1)/2]^n - (√5/5)*[(1-√5)/2]^n

 

    若有φ=(√5+1)/2、ψ=(1-√5)/2，则有

    f(n)=(φ^n-ψ^n)/√5

    所以 φ^n/√5 = f(n) + ψ^n/√5

    而ψ=(1-√5)/2，-1 < ψ < 0,则-1 < ψ^n < 1,则-√5/5 < ψ^n/√5 < √5/5

    又√5/5 < 1,所以f(n)是最接近φ^n/√5的整数