递归（Scala）

递归简单示例：

def test1(n:Int){ if(n>2){ test1(n-1) } println("n="+n) }

调用结果：

底层机制：

如图所示： 在栈中开辟一个函数栈test(4) 运行到test(3)时，在栈中开辟一个新的函数栈test(3)， 运行到test(2)时，在栈中开辟一个新的函数栈test(2)， 当n=2时，输出n=2,此时test(2)被销毁，回退到test(3) 输出n=3,test(3)被销毁，回退到test(4) 输出n=4,test(4)被销毁

---

递归的重要原则

程序执行一个函数时，就创建一个新的受保护的独立空间(新函数栈)函数的局部变量是独立的，不会相互影响递归必须向退出递归的条件逼近，否则就是无限递归当一个函数执行完毕，或者遇到 return，就会返回，遵守谁调用，就将结果返回给谁。

---

应用案例

案例1：斐波那契数

斐波那契数 1,1,2,3,5,8,13… 给你一个整数 n，请使用递归的方式，求出它的斐波那契数是多少？

object FibonacciDemo { def fibonacci(n: Int): Int = { if (n == 1 || n == 2) { 1 } else { fibonacci(n - 1) + fibonacci(n - 2) } } def main(args: Array[String]): Unit = { println(fibonacci(7)) } }

案例2

已知 f(1)=3; f(n) = 2*f(n-1)+1;请使用递归的思想编程，求出 f(n)的值?

package com.hnxy.recursive_package object RecursiveDemo02 { def func(n:Int):Int={ if(n==1){ 3 }else{ 2*func(n-1)+1 } } def main(args: Array[String]): Unit = { println(func(5)) } }

案例3

有一堆桃子，猴子第一天吃了其中的一半，并再多吃了一个！以后每天猴子都吃其中的一半，然后再多吃一个。当到第十天时，想再吃时（还没吃），发现只有 1 个桃子了。问题：最初共多少个桃子？ f(10)=1

package com.hnxy.recursive_package object RecursiveDemo03 { def eat(n:Int ):Int={ if(n==10){ 1 }else{ (eat(n+1)+1)*2 } } def main(args: Array[String]): Unit = { println(eat(1)) } }

---

使用递归的陷阱

以求斐波那契数为例，如果求fibonacci(50)，程序会变得异常慢，甚至挂掉。原因在于随着n的增加，递归次数会呈现指数增长的形式。因此，避免在递归代码中出现如 fibonacci(n - 1) + fibonacci(n - 2) 形式的多次递归调用。

object FibonacciDemo { def fibonacci(n: Int): Int = { if (n == 1 || n == 2) { 1 } else { fibonacci(n - 1) + fibonacci(n - 2) } } def main(args: Array[String]): Unit = { println(fibonacci(50)) } }