一、什么是递归

其实上节课讲到函数的最后，我们打了一个比方：把主程序中的顺序比喻成正常的时间顺序，遇到函数调用，即相当于做梦，可以跳出当前时空，做完梦之后又会回到做梦的时空处。有一些“梦”会比较有意思，在梦里继续做了同样的梦，这就叫做递归。
我们用最最浅显易懂的一个故事来说明：

老和尚讲故事

从前有座山，山里有座庙，庙里有个老和尚，在给小和尚讲故事。讲的什么故事呢？从前有座山，山里有座庙，庙里有个老和尚，在给小和尚讲故事。讲什么故事呢？从前有座山，山里有座庙，庙里有个老和尚，在给小和尚讲故事。讲的什么故事呢？从前有座山，山里有座庙，庙里有个老和尚，在给小和尚讲故事。。。。。。

说白了，就是自己调用自己，函数调用函数，再举一个比较饶舌的例子，关于递归的定义。

递归：
参见递归。
很迷糊，对吧，好吧，再具体一些。
递归：
如果还是没有明白递归是什么意思，参见“递归”。

其实说白了，就是“自己用自己”。在数学函数中，递归往往会很简单，有助于理解，譬如我们熟悉的阶乘运算，f(n)=n!，一般在数学上就定义成：
{
f(0)=1
f(n)=f(n-1) * n (n>=1)
}
如果我们用代码来实现一下，那是再简单不过的事情了。

#include <iostream>
using namespace std;

long long f(int x){
    if(x==0)
          return 1;
    return f(x-1) * x;
}

int main(){
  int n;
  cin>>n; // 此处n的规模应该很小，再大的话，需要考虑高精度算法
  cout<<(long long) f(n);  //暂时不考虑太大的数据
  return 0;
}

其实基本上就是照抄数学表达式，因此递归函数的关键在于理清思路，明确数学表达式，稍微要注意的一个问题时，递归一定要写清楚“终止条件”，像上面的例子，终止条件是x==0，如果没有终止条件，函数将无限递归......
如果对上面阶乘递归还不过清楚的话，可以参看下面的一个比喻：

皇帝（main函数）：大臣，你给我算一下f（3）。
大臣（调用f（3）的那个函数）：知府，你给我算一下f（2）。
知府（调用f（2）的那个函数）：县令，你给我算一下f（1）。
县令（调用f（1）的那个函数）：师爷，你给我算一下f（0）。
师爷（调用f（0）的那个函数）：回老爷，f（0）=1。
县令：回知府大人，f（1）=1。
知府：回大人，f（2）=2。
大臣：回皇上 ，f（3）= 6。
最终得到了结果，皇上满意了。

最后要注意的是，递归对我们理清思路和理解代码非常简单，但是反复的调用，对计算机的运算是一个噩梦，而且在递归运算中，往往会反复递归，反复运算，拜拜耗费大量的时间，另外从时间花销上，递归函数无疑是一个不太好的函数，对于运算次数较多（递归深度较深）时，我们往往不用递归，因为一般都会超时。

---

二、练习

1、斐波那契数。
2、输入一个非负整数，输出它的逆序数。如123，输出321。