开发者学堂课程【Scala 核心编程 - 进阶：使用递归的注意事项和陷阱】学习笔记，与课程紧密连接，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/610/detail/9101
使用递归的注意事项和陷阱
使用递归的注意事项
以求斐波拉契为例，来讲递归的注意事项是什么，先看递归求斐波拉契代码应该怎么写，叫 RecursiverFnb ,斐波那契是一个很厉害的人，为了纪念他将它的序列命令为斐波那契数列，学习斐波拉契数列直接写一个函数，写 fnb ，然后写一个( n ：bigint )表示将来会很大，但返回也是Bigint ，如果 n＝1或 n＝2则返回1，若 else 则fbn ( n-1 )＋ fbn ( n-2)。
接下来会出现什么现象呢，当传一个3进去，斐波拉契系数应该是1，1，2 ，3，5，以此类推，如果给一个3，返回一个2，没有问题，速度很快就出来了，再传一个10，速度也会很快55。
我们来研究一下，当我们使用斐波拉契阶层来处理求值时，观察递归的次数是如何增长的。
研究递归求斐波拉契的数的递归次数的增长情况。如现在整一个数，来把这个数传进去，把这个函数拎到里面，传一个全局变量去测试，先在这里面写一个非常大的数，var count ＝ Bigint ,初始化为0。此时，调用一次加1，调用递归的次数是把它加起来。
如果传3，递归次数可以看出是3，没问题，如果执行四次，调用次数会变成5，也很正常，五次时，会发现次数开始越来越快，当六时，递归次数变成15次，直接20次，递归一共是13529，求10时，递归次数为13529，求11时，只长了一个，调用次数的增长特恐怖，已经两万次了，因为这个地方要思考11过后里面会重复计算，增加了1，就变很多，几乎是从倍数增长，当30次时，会按照一两千万次的次数增长，30时，是160万好，当31时，200多万，当40次时，程序已经跑不起来了，代码会卡。
递归就不能这么用，由此可得出递归的次数呈现指数增长，增长的根本原因在于里面有两次调用。
如果不是有两次调用，而只是一次就不会指数增长。测一下求阶层，它的统计次数的增长只会增加一个，非常有效。求阶乘和这个最大区别在哪里？
假设不用斐波拉契，换用数测试时，降为了20次，若为40，应当为几千万次的调用，而这里50，只调用25次。因此在写递归时，要考虑出现重复计算，此时要考虑优化，优化的原则一般是改递归为迭代或使用其他办法减少递归次数。
package com.atguigu.chapter14
object RecursiveFnb {
def main(args:Array[string]):Unit={
var count =BigInt(0)
//1 1 2 3 5 ?
println(fbn(50)) // 10 -> 13529 11->21891
println("递归的次数是="+ count)
//研究下递归求斐波拉契的数的递归次数的增长情况!
//递归的次数是指数增长.
def fbn(n:BigInt): BigInt = {
count += 1
if(n==1|n==2)1
else fbn(n-1)+fbn(n-2)//重复计算，需要考虑优化->选代
}
}
有一篇文专门讲了对斐波拉契的优化，一共有多种方式，这里面简单了解。
https://blog.csdn.net/dadai/article/details/50209511
第一次直接改迭代，没有用递归，没有用递归了。
下面继续优化，递归调用，但是优化较好。
越到后面越不容易看懂，是迭代加递归结合使用，这里不是讲算法，讲完课程过后会专门讲数据算法，这里涉及到很多优化的方案，有些需要数学功底的。
这里主要强调递归时防止重复计算，如前面求最大值，求反转的写法绝对不会出问题，因为只有一次，求阶乘，速度也会很快，因为次数并不多，如500啊，BigInt可以算出的，它底层用了不是简单的一个数的存放，是字符串进行处理。如改为 n-2 ，就有重复计算，30时就无法计算。
package com.atguigu.chapter14
object RecursiveFactoria {
def main(args: Array[String]): Unit ={
println(factorial(30)) // 1*2*...10 =
}
//求出阶乘
def factorial(n: BigInt): BigInt =
if (n == 0) 1 else factorial(n - 2) * factorial(n - 1)
}
对于这样的问题，有一种学科专门来研究代码，它的执行的效率以及它递归的次数，叫数值分析，就是专门研究算法的程序必学的一门课程，专门研究代码的执行的效率高低，两个代码不用执行，就可通过数字分析来判断效率高低，因为主要是观察调用的次数，能计算出按什么样的规律来增长。
使用递归的注意事项，在开发时要注意，否则代码会出大问题。
