递归算法要素 |
您所在的位置:网站首页 › 函数有哪些要素和特征 › 递归算法要素 |
递归算法的三个要素。每次写递归,都按照这三要素来写,可以保证写出正确的递归算法! 1. 确定递归函数的参数和返回值: 确定哪些参数是递归的过程中需要处理的,那么就在递归函数里加上这个参数, 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。 2. 确定终止条件: 写完了递归算法, 运行的时候,经常会遇到栈溢出的错误,就是没写终止条件或者终止条件写的不对,操作系统也是用一个栈的结构来保存每一层递归的信息,如果递归没有终止,操作系统的内存栈必然就会溢出。 3. 确定单层递归的逻辑: 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
以下以二叉树前序遍历为例: 确定递归函数的参数和返回值:因为要打印出前序遍历节点的数值,所以参数里需要传入vector在放节点的数值,除了这一点就不需要在处理什么数据了也不需要有返回值,所以递归函数返回类型就是void,代码如下: void traversal(TreeNode* cur, vector& vec)确定终止条件:在递归的过程中,如何算是递归结束了呢,当然是当前遍历的节点是空了,那么本层递归就要要结束了,所以如果当前遍历的这个节点是空,就直接return,代码如下: if (cur == NULL) return;确定单层递归的逻辑:前序遍历是中左右的循序,所以在单层递归的逻辑,是要先取中节点的数值,代码如下: vec.push_back(cur->val); // 中 traversal(cur->left, vec); // 左 traversal(cur->right, vec); // 右
|
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |