常见算法思想3：递归法

递归法

在计算机编程应用中，我们常常遇到代码的递归调用，事实上，递归是一种编程技巧，它是分治思想的一种重要体现。递归算法对解决大多数问题是十分有效的，它能够使算法的描述变得简洁而且易于理解。

从直观上讲，递归是将大问题化为相同结构的小问题，从待求解的问题出发，一直分解到已经已知答案的最小问题为止，然后再逐级返回，从而得到大问题的解。

从本质上讲，计算机在执行递归调用时是一个不断压栈出栈的过程，递归的每一次“递”都是入栈，将函数状态或临时变量的指针入栈，而每一次“归”时都是出栈，将子问题的解逐渐交还给上层调用者。

递归算法有如下3个特点:

（1）递归过程一般通过函数或子过程来实现。
（2）递归算法在函数或子过程的内部，直接或者间接地调用自己的算法。
（3）递归算法实际上是把问题转化为规模缩小了的同类问题的子问题，然后再递归调用函数或过程来表示问题的解。

在使用递归法时，应该注意如下几点:

（1）递归是在过程或函数中调用自身的过程。
（2）在使用递归策略时，必须有一个明确的递归结束条件，这称为递归出口。
（3）递归算法通常显得很简洁，但是运行效率较低，所以一般不提倡用递归算法设计程序。
（4）在递归调用过程中，系统用栈来存储每一层的返回点和局部量。如果递归次数过多，则容易造成栈溢出，所以一般不提倡用递归算法设计程序。

方法实践

递归法生成斐波那契数：

// 递归生成斐波那契数
func Fibonacci(n uint) uint {
    if n <= 2 {
        return 1
    }
    return Fibonacci(n-1) + Fibonacci(n-2)
}

递归生成阶乘数

func Factorial(n uint)(result uint) {
    if (n > 0) {
        result = n * Factorial(n-1)
        return result
    }
    return 1
}

递推和递归虽然只有一个字的差异，但是两者之间还是不同的。递推像是多米诺骨牌，根据前面几个得到后面的；递归是大事化小，比如汉诺塔（Hanoi）问题，就是典型的递归。如果一个问题的求解既可以用递归算法求解，也可以用递推算法求解，此时往往选择用递推算法，因为递推的效率比递归高。