递归的基本概念

什么是递归？

递归就是自己调用自己，引用一个经典故事理解：

从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？“从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？‘从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？……’”

故事调用故事本身，层次越来越深……

使用递归的条件

1.问题本身可以分解为子问题，并且与原问题有相同的形式

2.递归必须要有边界条件，也就是递归出口

3.当边界条件（递归出口）不满足时，递归前进；当边界条件（递归出口）满足时，递归返回

编写递归函数的技巧

假设子问题已经解决！类似用数学归纳法解决数列问题时的a(n)与a(n+1)之间的关系，假设a(n)已知，计算a(n+1),然后追溯到a(0)已知，求a(1)……

例如：求n!

int function(int n)
{
    if(n==0)//0!=1
        return 1;
    else
        return function(n-1)*n;//n!=(n-1)!*n
}

总结一下也就是分成两部分

1.假设子问题已经解决，写出当前问题与子问题的递归关系；

2.写出边界条件的处理步骤(如:解决到最小问题时，即无法再递进时直接给出结果）。