通俗易懂读懂递归(简单的递归)
什么是递归？递归有什么用
一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。 一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。 注意： (1) 递归就是在过程或函数里调用自身; (2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。 递归算法一般用于解决三类问题： (1)数据的定义是按递归定义的。(Fibonacci函数) (2)问题解法按递归算法实现。(回溯) (3)数据的结构形式是按递归定义的。(树的遍历，图的搜索) 递归的缺点： 递归算法解题的运行效率较低。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。递归通俗的讲就是一个函数在其代码中反复调用自身。你应该知道菲波纳契数列，这个数列的定义是f(x)=1?(x=1)f(x)=2?(x=2)f(x)=f(x-1)+f(x-2) (x2)也就是说从第三项开始的每一项的值都等于是前两项之和。这在数学中叫递推数列--高中数学内容。
什么是递归？递归有什么用？
1、程序调用自身的编程技巧称为递归。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。
2、递归一般的作用用于解决三类问题：
(1)数据的定义是按递归定义的。（Fibonacci函数）
(2)问题解法按递归算法实现。
这类问题虽则本身没有明显的递归结构，但用递归求解比迭代求解更简单，如Hanoi问题。
(3)数据的结构形式是按递归定义的。
递归与非递归
首先要理解递归本身其实是一项非常重要的算法技巧。
递归满足两个条件：
1，不断调用函数本身，也就是递归函数。
2，调用是有限的，也就是递归出口。
为了理解方便，下面是用一个最简单的例子：求N的阶乘。
n!(阶乘)定义：
n!数学意思为n! = n*(n-1)! 1!=1;
其实根据上面递归定义结合分析下就可以n阶乘的递归算法：
1,构造一个递归函数,不断乘以自身和使用自身减一后调用同样函数．
2,定义出口，当函数参数等于1时结束;
如果用ISO C++语言描述如下：
int Factorial(int n){
if( n 1){
return n*Factorial(n-1);//递归函数调用
}
else if(n == 1){
return 1; //递归出口
}
else{
return ERROR;//报告输入错误
}
}
这里讨论主要的不是上面这个简单的例子，而是下面的一些改良．
因为递归设计大量的堆栈操作，所以一般都会考虑将递归转为非递归来执行．
这里用上面这个程序作一个分析例子来分析．
假设这里执行Factorial(4)，那么程序会按照下面方式来执行：
(1)执行Factorial(4)判断n 1执行Factorial(3),并且将Factorial(4)函数相关信息存入一个堆栈．
(2)执行Factorial(3)判断n 1执行Factorial(2),并且将Factorial(3)函数相关信息存入一个堆栈．
(3)执行Factorial(2)判断n 1执行Factorial(1),并且将Factorial(2)函数相关信息存入一个堆栈．
(4)执行Factorial(1)判断n == 1执行返回1;
(5)将Factorial(2)函数从堆栈中弹出，执行2*1，并且返回2．
(6)将Factorial(3)函数从堆栈中弹出，执行2*3，并且返回6．
(7)将Factorial(4)函数从堆栈中弹出，执行6*4，并且返回24．
如下图所示：
Factorial(4)
--Factorial(3);
--Factorial(2);
--Factorail(1);
--Factorail(1);
--Factorial(2);
--Factorial(3);
--结果
可以看到中间涉及的堆栈操作是很大的开销，每次需要保存当前函数的所有信息．
为了避免这样情况，可以使用下面这几种方法来实现递归到非递归的转换．
(1) 循环方法
循环方法是所有递归到非递归的转换中最理想的方法，可以将开销减少到最小．
不过也是分析起来最复杂的，对于简单的递归可以用这样的方法来处理．
例如：Factorial计算
这里回到n!(阶乘)定义上面来分析，这里将n!数学意思为n! = n*(n-1)! 1!=1;做一个扩展可以到到n!另外一个表示方法n! = n*(n-1)*(n-2)*....*1;
这样就可以很容易得到另外一个定义：
n!表示执行n次循环计算一个增量k，初始k=1和结果t=1;每次t乘以k++的值.
ISO C++实现代码如下：
Factorial(int n){
int k = 1 ;//增量
int t = 1 ;//临时结果
while(k!=n){
t*=k;
k++;
}
return t;
}
这样可以避免递归带来的大量堆栈操作．
(2) 自定义堆栈
对于复杂逻辑的堆栈操作，需要借助外部堆栈来实现．
因为对于所有的递归操作最后分析出来都是形成的一颗树形结构．
下面是一个递归实现Factorial的一个方法，虽然在这个程序中对比循环来相对复杂，不过对于一些不能分析出来循环的递归操作来说自定义堆栈的方法可以达到空间开销可控．
Factorial(int n){
Stack s;
int t = 1;//临时变量
s.push(n);
while(s.top()!=1)[
t *= s.top();
s.push(s.top()-1);
s.pop();
}
return t;
}
除了上面这两种方法外，还可以使用一种迭代的方法实现递归到非递归的处理．
在计算机算法中，迭代和递归是什么意思？它们有什么区别？
举个例子：我想求1+2+3+4+..+100的值。
迭代的做法：从1到100，顺着往下累加。1+2=3,3+3=6,6+4=10,10+5=15……
程序表示，
int i=1,sum=0;
while(i=100){
sum = sum +i;
}
递归的做法：我要求1到100的累加值，如果我已经得到1到99的累加值，将这个值加上100就是1到100的累加值；要得到1到99的累加值，如果已经得到1到98的累加值，将这个值加上99，就是1到99的累加值……最后我要得到1到2的累加值，我如果得到1自身累加值，再加上2即可，1自身的累加值显然就是1了。于是现在我们得到了1到2的累加值，将这个值加3就得到了1到3的累加值，……最后直到得到1到100的累加值。
程序表示，其中函数会调用自身，这就是递归方法的典型特征
int GetSum(int n)
{
if(n=0) return 0;
else return n+GetSum(n-1);
}
上述例子中，其实递归最后得到结果也是用迭代方法完成的，只是在程序的处理上直观看不出来。两者都能很好的完成计算任务，不同之处在于思维方式上，从而导致不同的计算方法：迭代是正向思维，从头到尾思考问题；递归是逆向思维，他假设我们已经得到了部分结果(假设我已经知道了1到99的累加值，把这个值加上100我们就得到了1到100的累加值了)，从尾部追溯到头部，从而让问题简化(当然这个例子中看不出来，这里只是方便理解，有兴趣可以参考一下 斐波那契数列 的构造方法)。
益学堂的都业华讲中枢理论，但我看原著时看到的递归是什么意思呢？
递归是原著中讲到的数学函数，我们不需要做过多研究探讨。都老师的课上是把原著中的数学公式、理论阐述成通俗易懂的方法以便大家理解的。
递归有什么特点？
递归函数的特点：函数定义中直接或间接地调用了本函数,必定存在可使递归调用终止的条件,否则导致出现无限递归。
函数定义中所具有的这些特点是判断函数是否为递归函数的基本要素。
绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的作用可以完全取代循环，因此在很多函数编程语言（如Scheme）中习惯用递归来实现循环。
扩展资料：
数据类型可以通过递归来进行定义，比如一个简单的递归定义为自然数的定义：“一个自然数或等于0，或等于另一个自然数加上1”。Haskell中可以定义链表为：
? ?
data?ListOfStrings?=?EmptyList?|?Cons?String?ListOfStrings
这一定义相当于宣告“一个链表或是空串列，或是一个链表之前加上一个字符串”。可以看出所有链表都可以通过这一递归定义来达到。
参考资料来源：百度百科——递归算法