递归

2024-07-16 18:12| 来源: 网络整理| 查看: 265

本文希望总结一下递归的用法和理解。

什么是递归

递归是什么呢？简单的说就是函数自身调用自身，可以间接调用也可以直接调用。在实际问题的解决中，调用递归可以把一个大型的问题层层转化成一个规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解。

在实际实现递归过程中，一定要理解“我们只需要关注一级递归的解决过程即可。”这句话的含义。可以把之前的多层递归体看成是一个总体，再考虑问题。

递归和迭代的区别

迭代和递归的区别是：迭代使用的是循环结构，递归使用的是选择结构。

递归能使程序的结构更清晰、更简洁、更容易让人理解，从而减少读懂代码的时间。但是大量的递归调用会建立函数的副本，会耗费大量的时间和内存。迭代则不需要反复调用函数和占用额外的内存。因此我们应该视不同情况选择不同的代码实现方式。递归的基本原理

第一：每一级的函数调用都有自己的变量。

第二：每一次函数调用都会有一次返回。当程序流执行到某一级递归的结尾处时，它会转移到前一级递归继续执行。

第三：递归函数中，位于递归调用前的语句和各级被调用函数具有相同的执行顺序。

第四：递归函数中，位于递归调用后的语句的执行顺序和各个被调用函数的顺序相反。

第五：虽然每一级递归都有自己的变量，但是函数代码并不会得到复制。

第六：递归函数中必须包含可以终止递归调用的语句。称为递归出口。

参见一个经典的例程说明上述：

1234567891011121314#includevoid up_and_down(int);int main(void){ up_and_down(1); return 0;}void up_and_down(int n){ printf("Level %d:n location %p\n",n,&n); /* 1 */ if(nrchild); }} 1234567891011121314151617/*1首先初始化待使用栈，然后将第一个结点入栈2然后只要栈不空，重复下面的操作：将栈顶元素弹出，然后看该元素是否访问过3若没访问过，则访问，置访问标记，然后将该元素的所有相邻顶点入栈（注意是全部，所以应用一个for或while循环来判断哪些元素该入栈）4重复2，直至全部顶点均被访问过。*/void PreorderNonRecursive(Bitree root){ stack stk; stk.push(root);//节点入栈 while(!stk.empty()){ p = stk.top();//栈顶元素出栈并且访问该节点 visit(p); stk.pop(); if(p.rchild) stk.push(p.rchild);//右边节点入栈 if(p.lchild) stk.push(p.lchild); }}

这里的非递归中使用栈将结点的相邻结点入栈就是模拟了递归中当一个结点被访问回退时，其相邻结点是和该结点处于同一层次的，故要一起入栈

【本文地址】

公司简介

联系我们