递归的实现过程

86 阅读 0 评论 57 点赞

我是靠谱客的博主安静泥猴桃，最近开发中收集的这篇文章主要介绍递归的实现过程，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

递归的概念：

程序调用自身的编程技巧称为递归（ recursion），把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解

简单理解就是分解-合并。分解是为了得到结果做准备，合并是把准备的资料合并成最终答案。通过传递参数，不断的更新当前调用函数的对象，直到达到目标位置，完成相关操作后，按原路返回到最初的位置。递归调用的总过程就是程序运行到某个点的时候，调用自身，这个时候，之前没运行完的程序会暂时不运行，等到下一层调用完了之后再运行。（可以理解为暂时停止当前任务，转而去做优先级更高的任务，完成后再转而继续之前的任务）
下面我们通过年龄的叠加来浅入分析递归的过程。

#include <stdio.h>
int Age_Recursion(int age){
if(age == 0){
return 0;
}else{
printf("---%d---n",age);//在下一个递归前打印当前age的值
return Age_Recursion(age-1)+age;
}
}
int main(){
int age = 4;
printf("%d",Age_Recursion(age));
return 0;
}

输出结果：
—4—
—3—
—2—
—1—
总和=10
Process returned 0 (0x0) execution time : 0.012 s

结合代码来看输出结果，根据我们长期学习数学的思维，一开始我们会认为函数总的执行过程是4+3+2+1+0；其实计算机递归总是逆着计算（想想栈的先进后出的特性）执行顺序为（（（（（0）+1）+2）+3）+4）。一个程序运行时自顶向下的，所以在一个函数里面出现递归时，那么他递归的顺序依旧是从函数的开头到相应逻辑递归的那一行，好比上面代码，在当前递归前总能打印当前age的值，因为它的执行在下一次递归之前。
我们再通过一张图片理解下：
这里写图片描述

从书上了解到递归过程是发散性的，就是在找到下一目标时并不一定是“两点一线”（如图所示），但为了方便理解，我们总是更在乎结果的获取，所以可以理想化的认为在自己调用自己的时候直接找到了目的对象。
图片出自百度

例如，我们可以试想自己在陌生的深山中，面对着多条岔路的选择方面，我们总不能期待运气爆棚，应该会试着选择其中一条，并给走过的路打上记号，当“走投无路了”，我很还可以跟着标记原路返回（就好比上图），避免做无用功。

实现方式：
函数调用主要依靠堆栈互动来实现的，递归调用也不例外，它的特点就是自己调用自己。在思考递归的时候可以用堆栈的思想去思考。
比如下面，我们通过二叉树的前序遍历的两种方式探讨递归的实现
前序遍历
a)递归方式:（部分代码）

void PreOrderTraversal( BinTree BT ){
if( BT ) {
printf(“%d”, BT->Data);
PreOrderTraversal( BT->Left );
PreOrderTraversal( BT->Right );
}
}

遍历过程

b)非递归方式（部分代码）

void InOrderTraversal( BinTree BT ){
BinTree T BT;
Stack S = CreatStack( MaxSize ); /*创建并初始化堆栈S*/
while( T || !IsEmpty(S) ){
while(T){ /*一直向左并将沿途结点压入堆栈*/
Push(S,T);
T = T->Left;
}
if(!IsEmpty(S)){
T = Pop(S); /*结点弹出堆栈*/
printf(“%5d”, T->Data); /*（访问） 打印结点*/
T = T->Right; /*转向右子树*/
}
}
}