递归的概念与例子

递归就是一个函数自己内部调用自己，同时具有一定的边界条件和边界值。
即，递归的两个要素：边界条件和递推公式。
递归可以有若干层，每一层有若干种情况。
递归可以理解为对所有层的每一种情况进行遍历。
一般格式：

int f(...)
{
    //边界条件（返回上一层）
    if(...)    return...; 
    //递推公式（在本层进行多种情况的选择，依次在各种情况下进入下一层）
    f(...);
}

例子：
递归求斐波那契数列：
已知边界条件：n[1]=1,n[2]=2，且递推公式：n[i]=n[i-1]+n[i-2](i>2)，则求斐波那契数列的代码为：

#include<iostream>
using namespace std;
int f(int i)
{
    if (i == 1 || i == 2)//边界条件
        return i;
    return f(i - 1) + f(i - 2);//递推公式
}
int main()
{
    int n;
    cin >> n;
    cout << f(n) << endl;
    return 0;
}

任何递归都可以转换为一个搜索树，整个递归的过程为对树的先序遍历。