递归概念

递归调用：一个函数在函数体内又调用了本身**
重要原则：

  • 程序执行一个函数时，就创建一个新的受保护的独立空间（即新函数栈）
  • 函数的局部变量是独立的，不会相互影响
  • 递归到最后一定可以退出，否则会陷入无限循环
  • 一个函数执行完毕或遇到 return，就会返回，谁调用就将结果返回给谁

注意：递归必须指定返回值类型，因为编译器无法推断出最终的返回值类型

应用案例

需求：有斐波那契数“1,1,2,3,5,8…”，给一个整数 n，求结果？（提示：正常递归或尾递归）

  1. object Fibonacci {
  2.   def main(args: Array[String]): Unit = {
  3.     println(fib(12))                        // 144
  4.     println(tailFib(12, 1, 1))    // 144
  5.   }
  7.   def fib(n: Int): Int = {
  8.     if (n == 1 || n == 2) {
  9.       1
  10.     } else {
  11.       fib(n - 1) + fib(n - 2)
  12.     }
  13.   }
  15.   def tailFib(n: Int, v1: Int, v2: Int): Int = {
  16.     if (n == 1 || n == 2) {
  17.       v2
  18.     } else {
  19.       tailFib(n - 1, v2, v1 + v2)
  20.     }
  21.   }
  22. }