《计算机程序的构造和解释》中的练习1.11:
函数f,如果n<3,那么f(n) = n;如果n>=3,那么 f(n)=f(n-1)+2f(n-2)+3f(n-3)
有了上面的公式可以,很容易发现f(n)的计算可以描述成一个“递归计算过程”,这里不再赘述。
我们还可以用“迭代计算过程”来计算f(n):
f(3)=f(2)+2f(1)+3f(0)
f(4)=f(3)+2f(2)+3f(1)
f(5)=f(4)+2f(3)+3f(2)
......
熟悉C、Java的同学肯定会说,这个“迭代计算过程”可以很简单地用一个for循环或者是一个while循环就解决了,
实际上,“迭代计算过程”也可以用“递归程序”来描述,这里可能会让人有点困惑,需要明白的是,“递归计算过程”
和“递归程序”不是一回事儿,前者是“计算”层面上的递归,后者是语法层面上的,好了不多说了,直接看程序吧:
object fn { def f(n:Int)={ def loop(a:Int,b:Int, c:Int ,counter:Int):Int ={ if(n<3) n else if(counter<=n) loop(a+2*b+3*c,a,b,counter+1) else a } loop(2,1,0,3) } def main(args:Array[String])={ println(f(0)) println(f(1)) println(f(2)) println(f(3)) println(f(4)) println(f(5)) } }