《计算机程序的构造和解释》中的练习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))
  }
}
05-03 23:18