3.6 递归函数
在编程语言中，如果函数直接或间接调用函数自身，则该函数被称为递归（Recursion）函数。递归作为一种算法在编程语言中被广泛应用。有些现实问题不借助递归的话，求解过程会非常复杂。
3.6.1 使用递归函数求解斐波那契数列
递归往往只需少量的代码就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有退出条件，否则会进入无限循环而无法退出。
举一个数学中的例子，斐波那契数列是：1，1，2，3，5，8，13，21，34，55，89，144……以此类推，我们会发现在这个数列中，后一个数等于前面两个数之和（1=1+0，2=1+1，3=1+2……）。这个数列的规律在自然界中也很有代表性，如兔子自然繁殖数量的规律。
如果想求解斐波那契数列，那么最直接的方式是借助递归函数来求解。首先分析数列的递归表达式：
此函数解析式是一个分段函数，其中第二段是一个递归函数，需要函数调用自身。下面是递归函数求解斐波那契数的示例程序3-8。
示例程序3-8 递归函数实现斐波那契数列：chapter03\code08\func.go
在示例程序3-8中，第04行定义了一个名为fib的函数，接收一个int64类型的变量，同时返回一个int64类型的值。第05～07行用到了逻辑控制中的if条件判断，其中if n <=1是递归的退出条件。第08行是体现递归的地方，fib函数调用自身。
注意
Go语言中不支持匿名函数的递归，如果将一个匿名函数赋值给一个变量，那么在匿名函数内部访问这个变量会出现未定义的错误。
一般来说，在编程语言中，函数调用是通过栈（Stack）这种数据结构来实现的：每当进入一个函数调用，栈就会加一层栈帧；每当函数调用结束后返回，栈就会减一层栈帧。由于栈的大小是有限的，因此如果递归调用的次数过多，就可能会导致栈内存溢出的情况。另外，由于递归中间的临时运算结果并没有暂存，因此计算速度也比较慢。
递归函数虽然可以简化程序，让程序代码更加具有可读性，但是如果递归的调用层次过多，那么执行效率会非常低，也非常耗时，例如用递归计算fib(50)会非常耗时。此时需要用其他的非递归方式来实现，以提高效率。
3.6.2 使用循环代替递归的方法
递归函数也可以利用非递归的方法来实现。下面给出计算斐波那契数列的非递归改进版本，以提高计算速度，如示例程序3-9所示。
示例程序3-9 用非递归函数来实现斐波那契数列：chapter03\code08\func2.go
在示例程序3-9中，实际上是用循环的方式来替换递归的方式，由于中间的值都暂存在临时变量中，因此这种方式的计算效率与递归方式的计算效率要高不少。