头歌实践教学平台java常用集合答案 头歌educoder实训作业答案递归 |
您所在的位置：网站首页 › educoder实训平台答案c › 头歌实践教学平台java常用集合答案 头歌educoder实训作业答案递归 |
|
深入理解递归1. 递归是什么？查词典头递归和尾递归案例1:求N的介乘2. 递归与分治法3. 解递归题的关键4. 解决递归题的套路5. 诀窍案例2：反转链表案例3：跳台阶案例4：反转二叉树参考链接 1. 递归是什么？ 在数学和计算机科学中，递归是指在函数的定义中调用自身函数的方法。 查词典为了更加理解什么是递归。 我们可以把日常生活中使用词典的过程看做递归。 即为了解释一个词，需要使用更多的词。 比如：当你查一个词时，发现这个词的解释中某个词依然不懂，于是你开始查这第二词。可惜，第二词的解释中仍然有不懂的词，于是查第三个词，（递）： 这样查下去，直到有个词的解释你是完全能看懂的，那么递归走到了尽头，然后你开始后退 （归），逐个明白之前查过的每一个词。最终，你明白了最开始那个词的意思。 头递归和尾递归按照递归的使用方法，递归分成两类：1. head recursion； 2. tail recursion. 头递归（Head Recursion） 默认情况下，我们都用头递归。 在调用函数自身后，才做其他计算操作。这需要把函数调用和计算结果缓存到栈中，要使用更多内存空间。 所以头递归比循环要慢两倍左右，性能更慢。它需要把原问题先挨个展开成子问题，直到遇到底部。然后回溯，合并子问题的结果。 尾递归（Tail Recursion） 在递归函数内，先做计算操作，在函数末尾调用函数自身。类似于循环遍历，所以性能更高。下面看看一个案例，初步认识什么是递归函数。案例1:求N的介乘求N的介乘 输入： n = 3 输出：n = 3 * 2 * 1 = 6 输入： n = 5 输出： n = 5 * 4 * 3 * 2 * 1 = 120 子问题：大小相邻数相乘。 用头递归和尾递归分别解答这个题目。代码如下： package Recursion; public class HeadAndTailRecursion { public static void main(String[] args) { System.out.println(recursionHead(3)); System.out.println(recursionTail(3, 1)); } /** * Head recursion 递归过程 * 递： * //1 * // 2* recursionHead(1) * // 3 * recursionHead(2) ** 归： * // 2 * 1 * // 3 * 2 * //6 * * @param N * @return */ private static int recursionHead(int N) { if (N 2 -> 3 -> 4 -> 5 -> null 输出结果： 5 -> 4 -> 3 -> 2 -> 1 -> null 发现重复的子问题：当前节点和前一个节点进行反转。 暴力递归遍历链表，当遇到节点的next为空，则返回尾节点。 在递归的回溯过程中（把当前节点与前一个节点进行反转），回归到原链表的首部节点，指针指向null。具体演示过程如下： 递： recursion(1,null) recursion(2, 1) recursion(3, 2) recursion(4, 3) recursion(5, 4) recursion(null, 5) 归: 5->4 4->3 3->2 2->1 1->null返回：Node（5） 从上图推导过程，可得递归函数recursion(cur, pre) private ListNode recursion(ListNode cur, ListNode pre) { if(cur == null) {//终止条件 return pre; } ListNode res = recursion(cur.next, cur);//分解子问题，推导递推公式。 cur.next = pre; return res; }案例3：跳台阶案例4：反转二叉树
|
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |