递归


递归(Recursion)是在函数中调用自身,调用者会先置入内存栈,被调用者执行完后,再从栈取出被置入的函数继续执行。栈(Stack)是一种「先进后出」的数据结构,就好比将书本置入箱中,最先放入的书会最后才取出。

C++ 支持函数递归调用,递归之目在于执行重复任务,例如,求最大公因数可以使用递归,下面的程序是使用递归来求最大公因数的范例:

#include <iostream> 
using namespace std; 

int gcd(int, int); 

int main() { 
    int m = 0;
    int n = 0; 

    cout << "输入两数:"; 
    cin >> m >> n; 

    cout << "GCD: " << gcd(m, n) << endl; 

    return 0; 
} 

int gcd(int m, int n) { 
    if(n == 0) {
        return m; 
    } 
    else { 
        return gcd(n, m % n); 
    }
}

执行结果:

输入两数:30 32
GCD: 2

上面的程序是使用辗转相除法来求最大公因数;可以使用递归求解的程序,基本上也可以使用循环求解,例如下面的程序就是最大公因数的循环求解方式:

#include <iostream> 
using namespace std; 

int gcd(int, int); 

int main() { 
    int m = 0;
    int n = 0; 

    cout << "输入两数:"; 
    cin >> m >> n; 

    cout << "GCD: " << gcd(m, n) << endl; 

    return 0; 
} 

int gcd(int m, int n) { 
    int r = 0; 

    while(n != 0) { 
        r = m % n; 
        m = n; 
        n = r; 
    } 

    return m; 
}

那么使用递归还是使用循环求解?这没有一定的答案,也有看程序语言是否可以做递归最佳化,因为递归函数会在内存中栈,语言会有栈的数量限制,若递归最佳化能展开递归,转为循环形式,可以避开这类限制。

这么说来,使用循环比较好?并非如此,开发者很容易在循环执行过多的任务,令循环难以阅读、理解与维护,特别是令那些本质上可以分而治之的任务,难以抽取、并行化,或者令源码本质上其实重复的流程,难以辨识出来。


展开阅读全文