开发者学堂课程【Scala 核心编程-基础：函数递归调用的机制】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/609/detail/8931
函数递归调用的机制
内容介绍
一、递归调用快速入门
二、总结
一、递归调用快速入门
这节课讲解递归，函数中递归使用比较多，而且马丁也推荐使用递归，递归即一个函数在函数体内又调用了本身，则称为递归调用。
1、当调用 test(4)时
观察如下代码:
deftest (n: Int) {
if(n>2) {
test(n- 1)
}
printin("n="+n) //
}
如上这个代码写了一个函数接收 n，如果 n<2，进行计算 test(n-1)，打印 print，那么当调用 test(4)时 print 应该输出什么？下面进行递归代码的分析，如图：
根据之前讲解的原则，一旦有一个函数就会开辟一个新的栈空间，所以内存中会开辟一个main栈，栈中调用test(4)，还会开辟一个 test 空间，会接收到 n=4，然后再代码中执行判断 n>2是否成立，显然4>2成立，所以 test 栈会执行test 中的代码，进行调用 test(n-1)，就是调用 test(3)，而 print 不会进行输出，因为紧接着又会开辟一个 test(3)空间，此时 n=3，然后逻辑继续执行，判断3>2，然后继续执行后得到 test(2)，print 仍然待执行，而 test(2)为一个函数，所以再次开辟 test(2)栈空间，此时 n=2，而判断条件 n>2则不再成立，于是执行 print 输出 n，显然会输出 n=2。
此时栈顶到了 test(2)，等到 test(2)执行完毕栈顶就回到了 test(3)，进行执行 test(3)的 print，这时打印的 n 为test(3)中的 n，为 n=3，执行完毕后再往下执行 test(4)中的 print，打印 n=4，然后回到 main 栈执行，而 main 主栈一旦执行完毕整个栈就全部销毁。所以最后输出为2，3，4，然后运行代码进行验证，如下:
package com. atguigu. chapter05. recursive
object Demo01 {
def main(args: Array[String]): Unit = {
test(4)
def test (n: Int) {
if(n>2){
test (n - 1)
}
println("n=" + n) //
}}
运行结果如下：
D: \program\jdk8 \bin \java
n=2
n=3
n=4
说明分析正确。
2、当调用 test2(4)时
那么如下代码，如果调用 test2(4)也输入值为4的话，最后输出结果是什么？
def test2 (n: Int) {
if(n>2){
test2 (n - 1)
}else {
println("n=" + n)
}
此时只能输出一个结果，因为这个结果是 else，else 只有在 test(2)时有机会进入栈，然后执行 print，而没有其他机会进行输出。代码运行如下：
package com. atguigu. chapter05. recursive
object Demo01 {
def main(args: Array[String]): Unit = {
test2(4)
def test (n: Int) {
if(n>2){
test (n - 1)
}
println("n=" + n) //
}
def test2 (n: Int) {
if(n>2){
test2 (n - 1)
}else {
println("n=" + n)
}
}}
运行结果如下：
D: \program\jdk8 \bin \java
n=2
说明分析验证成功。
递归是后面学习大数据常用到的一种写法，一定要学懂。
二、总结
根据上面学习的函数递归调用总结需要遵守的重要原则如下 :
1、当程序执行一个函数时，就创建一个新的受保护的独立空间(新函数栈)。比如在上面案例中一旦调用了 test就会开辟一个新的空间，而这个空间是属于栈的但又是独立的。
2、函数的局部变量是独立的，不会相互影响。在将来做开发时可能面对传入的值不是基本值类型，而是引用类型，就可能会出现有一个堆，比如在主栈中创建了一个对象 obj，但 obj 的数据并不在 main 栈中，而是在堆当中，所以obj 因为种种原因就指到了堆当中，而如果把 obj 传给 test(3)栈，test(3)栈则也有可能执行堆，甚至在堆当中还可以存入一个栈，就像 struts2拦截器实现的底层机制就是把一个对象放到栈中，然后不停的开栈，每一个栈都有机会去修改这个对象。在以前讲 java 的数据结构时讲解过迷宫回溯，递归中有很多递归，在堆当中有很多老鼠在找迷宫，那个老鼠先找到就发一个信号，然后全部进行退出，其实这个也能实现这种堆栈的效果。如图：
所以如上函数的局部变量是独立的，不会相互影响的，如果受到影响则是引用类型。
3、递归必须向退出递归的条件逼近，否则就是无限递归。比如上面讲的代码，只有 test（n-1）才会出现 n 不再大于2，才能进行退出，如果改为 test（n+1）然后进行运行，如：
…
if(n>2){
test (n + 1)
}
…
运行结果如下：
D: \program\jdk8\bin\java
Exception in thread "main" java.lang . Stac koverflowError
at com. atguigu. chapter05. recursive . Demo01$. test (Demo01.scala:9)
at com. atguigu. chaptero5. recursive . Demo01$. test (Demoo1.scala:9)
……
运行结果提示出现栈溢出，并且不停的进行输出。栈内存就会不停的往上走开辟栈空间，导致死归，如图：
所以写递归时特别重要的东西就是如何去判断退出递归的条件，像二分查找中也有递归。
4、当一个函数执行完毕，或者遇到 return 就会返回，遵守谁调用，就将结果返回给谁的机制。比如上面讲的案例，在 test(4)执行完毕后，遵循谁调用就返回给谁的机制，所以将结果返回给 test(3)。
