SICP学习笔记03 vvipi 发表于2018年11月8日,阅读:2111 #### 练习1.11 函数f由如下规则定义:如果 n<3 那么 f(n)=n ;如果 n≥3 ,那么f(n)=f(n−1)+2f(n−2)+3f(n−3)。分别写出采用递归和采用迭代计算f的过程。 #### 解答 ```scheme (define (recfn x) (if (< x 3) x (+ (recfn (- x 1)) (* 2 (recfn (- x 2))) (* 3 (recfn (- x 3)))))) (define (iterfn alpha beta gama counter x) (if (> counter x) gama (iterfn beta gama (if (< counter 3) counter (+ (* 3 alpha) (* 2 beta) gama)) (+ counter 1) x))) (define (print x) (display "result of recfn ") (display x) (display " is ") (display (recfn x)) (display ", result of iterfn ") (display x) (display " is ") (display (iterfn 0 0 0 0 x)) (display "\n")) (print 0) (print 2) (print 3) (print 4) (print 5) (exit) ``` #### 理解 f(0) = 0 f(1) = 1 f(2) = 2 f(3) = f(2) + 2f(1) + 3f(0) f(4) = f(3) + 2f(2) + 3f(1) ...... 3以后的fn都是由前3个结果计算而来,因此想到用3个参数来记录前3个结果,再加上计数的counter和需要计算的x来构造这个函数。每次迭代,就把上次的计算结果左移一格,去掉最小的,再计算一个新的结果。 确实如书中所说,递归的思路很容易表达,迭代的就要花点心思。scheme里面没有for循环,全部靠递归。循环被称为只是语法糖,可是吃惯糖的突然用起如此返璞归真的语法,真是有些苦涩呢。 在函数内部不知道怎么直接赋值,只能靠参数传值,一个不复杂的思路,硬是表达了快一个小时才运行通过。 为了方便调试,在vs code中安装了code runner来运行代码,写完直接按ctrl+alt+n看结果还是比较方便的。