江苏龙网

  1. 首页 > 人文 > >

程序员必备的基本算法：递归详解( 二 )

//n的阶乘（n为大于0的自然数）int factorial (int n){}2.寻找递归终止条件递归的一个典型特征就是必须有一个终止的条件 ， 即不能无限循环地调用本身 。 所以 ， 用递归思路去解决问题的时候 ， 就需要寻找递归终止条件是什么 。 比如阶乘问题 ， 当n=1的时候 ， 不用再往下递归了 ， 可以跳出循环啦 ， n=1就可以作为递归的终止条件 ， 如下：
//n的阶乘（n为大于0的自然数）int factorial (int n){if(n==1){return 1;}}3.递推函数的等价关系式递归的「本义」 ， 就是原问题可以拆为同类且更容易解决的子问题 ， 即「原问题和子问题都可以用同一个函数关系表示 。 递推函数的等价关系式 ， 这个步骤就等价于寻找原问题与子问题的关系 ， 如何用一个公式把这个函数表达清楚」 。 阶乘的公式就可以表示为 f(n) = n * f(n-1), 因此 ， 阶乘的递归程序代码就可以写成这样 ， 如下：
int factorial (int n){if(n==1){return 1;}return n * factorial(n-1);}「注意啦」 ， 不是所有递推函数的等价关系都像阶乘这么简单 ， 一下子就能推导出来 。 需要我们多接触 ， 多积累 ， 多思考 ， 多练习递归题目滴~
leetcode案例分析来分析一道leetcode递归的经典题目吧~
?
原题链接在这里哈：
?
「题目：」 翻转一棵二叉树 。
输入：
4/\27 / \/ \13 69输出：
4/\72 / \/ \96 31我们按照以上递归解题的三板斧来：
「1. 定义函数功能」
函数功能（即这个递归原问题是） ， 给出一颗树 ， 然后翻转它 ， 所以 ， 函数可以定义为：
//翻转一颗二叉树public TreeNode invertTree(TreeNode root) {}/** * Definition for a binary tree node. * public class TreeNode { *int val; *TreeNode left; *TreeNode right; *TreeNode(int x) { val = x; } * } */「2.寻找递归终止条件」
这棵树什么时候不用翻转呢？当然是当前节点为null或者当前节点为叶子节点的时候啦 。 因此 ， 加上终止条件就是：
//翻转一颗二叉树public TreeNode invertTree(TreeNode root) {if(root==null || (root.left ==null}}「3. 递推函数的等价关系式」
原问题之你要翻转一颗树 ， 是不是可以拆分为子问题 ， 分别翻转它的左子树和右子树？子问题之翻转它的左子树 ， 是不是又可以拆分为 ， 翻转它左子树的左子树以及它左子树的右子树？然后一直翻转到叶子节点为止 。 嗯 ， 看图理解一下咯~
程序员必备的基本算法：递归详解文章插图
首先 ， 你要翻转根节点为4的树 ， 就需要「翻转它的左子树（根节点为2）和右子树(根节点为7）」 。 这就是递归的「递」的过程啦
程序员必备的基本算法：递归详解文章插图
然后呢 ， 根节点为2的树 ， 不是叶子节点 ， 你需要继续「翻转它的左子树（根节点为1）和右子树（根节点为3）」 。 因为节点1和3都是「叶子节点」了 ， 所以就返回啦 。 这也是递归的「递」的过程~
程序员必备的基本算法：递归详解文章插图
同理 ， 根节点为7的树 ， 也不是叶子节点 ， 你需要翻转「它的左子树（根节点为6）和右子树（根节点为9）」 。 因为节点6和9都是叶子节点了 ， 所以也返回啦 。
程序员必备的基本算法：递归详解文章插图
左子树（根节点为2）和右子树(根节点为7）都被翻转完后 ， 这几个步骤就「归来」 ， 即递归的归过程 ， 翻转树的任务就完成了~


推荐阅读


上一篇：图解｜零拷贝Zero-Copy技术大揭秘

下一篇：嵌入式软件测试的基本方法