旅行社网站 模板,怎么看网站做没做推广,邯郸市丛台区最新疾情,wordpress 微信导航站递归为什么这么难#xff1f;一篇文章带你了解递归
美国计算机科学家——彼得多伊奇(L Peter Deutsch)在《程序员修炼之道》(The Pragmatic Programmer)一书中提到“To Iterate is Human, to Recurse, Divine”——我理解的这句话为#xff1a;人理解迭代#xff0c;神理解…递归为什么这么难一篇文章带你了解递归
美国计算机科学家——彼得·多伊奇(L Peter Deutsch)在《程序员修炼之道》(The Pragmatic Programmer)一书中提到“To Iterate is Human, to Recurse, Divine”——我理解的这句话为人理解迭代神理解递归。
毋庸置疑递归的代码是非常简洁的但是想要理解递归也是非常不容易的本文介绍了递归的常见场景与例题和递归的基本用法与思想希望能帮助新人理解递归的思想相信看完这篇文章再动手敲一下代码一定对递归有更加深入的了解。
文章列举了一些递归的经典操作包括斐波纳契数列、汉诺塔、冒泡排序的递归写法。以及力扣的一些链表的练习题使用递归去完成——206. 反转链表 - 力扣LeetCode、203. 移除链表元素、19. 删除链表的倒数第 N 个结点、83. 删除排序链表中的重复元素、82. 删除排序链表中的重复元素 II、21. 合并两个有序链表、23. 合并 K 个升序链表。
首先让我们思考
什么是递归递归的思想是什么怎么使用递归使用递归应该注意什么问题递归的时间复杂度应该怎么计算
一、什么是递归
在计算机中递归(Recursion)是指在函数的定义中使用函数自身的方法。实际上递归顾名思义其包含了两个意思递 和 归。
二、递归的思想是什么
既然叫做递归那么肯定分为“递”与“归”。 递归的基本思想就是将大规模问题转为小规模问题问题一直被不断缩小一直递归到符合结束条件为止。
因为每次递归都是相同的函数所以很重要的一件事是寻找到递归的条件找到应该如何解决大问题和小问题的同一个方法。
三、怎么使用递归
我们在了解了递归的基本概念以后就需要思考递归应该怎么用
首先需要明确递归的三要素 明确递归终止条件 递归既然有去有回那么必须有一个明确的结束条件。当到达这个条件递归就会终止。 给出递归终止时的处理办法 当递归结束时递归函数每一次返回值都需要有处理的方法我们需要在这里给出问题的解决方法。 提取重复的逻辑缩小问题规模。找出递归关系式 寻找一个递归的关系如何将这个问题不停分解为小问题。
注意判断“递”还是“归” 判断是在“递”的过程中解决问题还是在“归”的过程中解决问题 四、使用递归应该注意什么
首先我们要知道递归有两种模型。
1、在“递”的的过程中解决问题。
{1、递归结束条件2、问题的解决方法3、递归的等价关系缩小规模的方法。
}2、在“归”的的过程中解决问题。
{1、递归结束条件2、递归的等价关系缩小规模的方法。3、问题的解决方法
}这两种模型都是属于单路递归的模型既然有单路递归那么肯定会有多路递归。
在之后的经典场景分析会介绍到冒泡排序的递归写法就是单路递归。汉诺塔、斐波纳契数列就是属于多路递归。
五、递归的时间复杂度怎么计算
若有递归式 T ( n ) a T ( n b ) f ( n ) T(n) aT(\frac{n}{b}) f(n) T(n)aT(bn)f(n) 其中 T ( n ) T(n) T(n) 是问题的运行时间 n n n 是数据规模 a a a 是子问题个数 T ( n b ) T(\frac{n}{b}) T(bn) 是子问题运行时间每个子问题被拆成原问题数据规模的 n b \frac{n}{b} bn$ f(n)$ 是除递归外执行的计算
令 x log b a x \log_{b}{a} xlogba即 x log 子问题缩小倍数 子问题个数 x \log_{子问题缩小倍数}{子问题个数} xlog子问题缩小倍数子问题个数
那么 T ( n ) { Θ ( n x ) f ( n ) O ( n c ) 并且 c x Θ ( n x log n ) f ( n ) Θ ( n x ) Θ ( n c ) f ( n ) Ω ( n c ) 并且 c x T(n) \begin{cases} \Theta(n^x) f(n) O(n^c) 并且 c \lt x\\ \Theta(n^x\log{n}) f(n) \Theta(n^x)\\ \Theta(n^c) f(n) \Omega(n^c) 并且 c \gt x \end{cases} T(n)⎩ ⎨ ⎧Θ(nx)Θ(nxlogn)Θ(nc)f(n)O(nc)并且cxf(n)Θ(nx)f(n)Ω(nc)并且cx
例1 T ( n ) 16 T ( n 4 ) n 2 T(n) 16T(\frac{n}{4}) n^2 T(n)16T(4n)n2 a 16 , b 4 , x 2 , c 2 a16, b4, x2, c2 a16,b4,x2,c2此时 x 2 c x2 c x2c时间复杂度 Θ ( n 2 log n ) \Theta(n^2 \log{n}) Θ(n2logn)
例2 二分查找递归
int f(int[] a, int target, int i, int j) {if (i j) {return -1;}int m (i j) / 1;if (target a[m]) {return f(a, target, i, m - 1);} else if (a[m] target) {return f(a, target, m 1, j);} else {return m;}
}子问题个数 a 1 a 1 a1子问题数据规模缩小倍数 b 2 b 2 b2除递归外执行的计算是常数级 c 0 c0 c0 T ( n ) T ( n 2 ) n 0 T(n) T(\frac{n}{2}) n^0 T(n)T(2n)n0
此时 x 0 c x0 c x0c时间复杂度 Θ ( log n ) \Theta(\log{n}) Θ(logn)
六、递归的实战
遇见递归请不要害怕只是因为你做题少了而已。做完这些题一定对递归的感悟会更深刻。
1、基本运算中的递归
a、冒泡排序的递归写法
public class bubble {public static void main(String[] args) {int a[] {1, 5, 7, 2, 0, 3, 6};Bubble(a, a.length - 1);for (int i : a) {System.out.println(i);}}public static void Bubble(int[] a, int len) {//1、递归结束条件if (len 0) return;//2、处理方法for (int i 0; i len; i) {if (a[i] a[i 1]) {int temp a[i];a[i] a[i 1];a[i 1] temp;}}//3、递归关系缩小问题规模Bubble(a, len - 1);}
}通过这个简单算法可以看出这个就属于在递的过程中解决问题的模型。
我们逐轮分析
初始数据{1, 5, 7, 2, 0, 3, 6}
第一轮找到最大的数进行下沉得到{1, 5, 2, 0, 3, 6,7}将7移动到最后一位那么第二轮就不需要对7进行排序。
第二轮找到最大的数进行下沉因为上一轮已经找到7,那么这一轮只需要找7前面的数就行了得到{1, 5, 2, 0, 3, 6,7}那么第三轮就不需要对6进行排序。
b、汉诺塔的实现 通过这个移动过程我们很容易找到一个移动规律具体就不多说了代码如下
import java.util.LinkedList;public class Hanoi {static LinkedListInteger a new LinkedList();static LinkedListInteger b new LinkedList();static LinkedListInteger c new LinkedList();public static void main(String[] args) {long startTime System.nanoTime();init(3);long ebdTime System.nanoTime();print();}private static void print() {System.out.println(**************************);System.out.println(a);System.out.println(b);System.out.println(c);}/*** 汉诺塔的递归* param n 塔的层数* param a 原* param b 借* param c 目标*/public static void towerOfHanoi(int n,LinkedListInteger a,LinkedListInteger b,LinkedListInteger c){//结束条件if (n 0){return;}//等价关系towerOfHanoi(n-1,a,c,b);//处理方法c.add(a.removeLast()); //将a移动到c//等价关系towerOfHanoi(n-1,b,a,c);}public static void init(int n){for (int i n; i1; i--){a.add(i);}System.out.println(a);towerOfHanoi(n,a,b,c);}
}c、斐波纳契数列
如果不知道斐波纳契的具体请看这篇文章——用C语言写爬楼梯斐波那契数列的应用迭代与递归爬楼梯问题超详细看完这一篇就够了。就不多赘述了这里主要介绍一下在递归中的减枝操作。
未减枝前的递归分解过程 可以看到颜色相同的是重复的 f ( 3 ) f(3) f(3) 重复了 2 次 f ( 2 ) f(2) f(2) 重复了 3 次 f ( 1 ) f(1) f(1) 重复了 5 次 f ( 0 ) f(0) f(0) 重复了 3 次
随着 n n n 的增大重复次数非常可观如何优化呢
Memoization 记忆法也称备忘录是一种优化技术通过存储函数调用结果通常比较昂贵当再次出现相同的输入子问题时就能实现加速效果改进后的代码
public class Fibonacci {public static void main(String[] args) {Scanner cin new Scanner(System.in);for (int i 1; i 30; i) {System.out.println(pruning(i));}}力kou//进行剪枝public static int pruning(int n){int[] cache new int[n1];Arrays.fill(cache,-1);cache[0] 0;cache[1] 1;return f(n,cache);}public static int f(int n,int[] cache) {if (cache[n] ! -1){return cache[n];}cache[n] f(n - 1,cache) f(n - 2,cache);return cache[n];}
}
在这儿我们使用了一个数组去保存了重复的运算结果。 2、链表操作的递归
在使用递归进行链表的操作时希望大家牢记这句话
在链表的递归过程中以单个结点操作的思想递归
a、206. 反转链表 - 力扣LeetCode /*** 递归实现反转链表在同一个链表上反转** param head 待反转链表* return 反转后的新头节点*/public ListNode reverseList(ListNode head) {//递归结束条件if (head null || head.next null) {return head;}ListNode list reverseList2(head.next);//操作链表进行反转head.next.next head;head.next null;System.out.println(list);return list;}b、203. 移除链表元素 /*** 使用递归的方法进行删除指定数据** param head 待处理链表* param val 待删除值* return 处理完成的链表*/public ListNode removeElements(ListNode head, int val) {if(head null){return null;}if(head.val val){//如果是删除该节点那么就相当于返回下一个节点的递归结果// 此时上一个节点就会避开当前节点而去链接下一个节点return removeElements1(head.next,val);}else {//当前节点链接到后面的链表head.next removeElements1(head.next,val);return head;}}c、19. 删除链表的倒数第 N 个结点 /*** 使用递归的方法* param head* param n* return*/public int recursion(ListNode head, int n){if(head null){return 0;}int nth recursion(head.next,n);//下一个节点的位置if (nth n){//判断出下一个节点的的位置刚好是需要被删除的节点head.next head.next.next;}return nth1; //当前节点的位置}d、83. 删除排序链表中的重复元素 /*** 使用递归的方法** param head 待处理链表* return 处理完成的链表*/public static ListNode deleteDuplicates1(ListNode head) {if (head null || head.next null) {return head;}if (head.val head.next.val) {return deleteDuplicates1(head.next);} else {head.next deleteDuplicates1(head.next);return head;}}e、82. 删除排序链表中的重复元素 II /*** 使用递归的方法** param head 待处理链表* return 处理完成的链表*/public ListNode deleteDuplicates(ListNode head) {if (head null || head.next null) {return head;}if (head.val head.next.val) {//如果一直相同则不停移动指针一直到找到不相同的节点为止ListNode t head.next.next;while (t ! null t.val head.val) {t t.next;}return deleteDuplicates(t);} else {head.next deleteDuplicates(head.next);return head;}}f、21. 合并两个有序链表 /*** 使用递归的方法进行合并链表** param list1* param list2* return 返回添加以后的链表*/public ListNode mergeTwoLists1(ListNode list1, ListNode list2) {if(list1 null){return list2;}else if (list2 null){return list1;}if(list1.val list2.val){list1.next mergeTwoLists1(list1.next,list2);return list1;}else {list2.next mergeTwoLists1(list1,list2.next);return list2;}}g、23. 合并 K 个升序链表 /*** 合并两个有序链表** param list1* param list2* return*/public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {if (list1 null) {return list2;} else if (list2 null) {return list1;}if (list1.val list2.val) {list1.next mergeTwoLists(list1.next, list2);return list1;} else {list2.next mergeTwoLists(list1, list2.next);return list2;}}/*** 合并K个有序链表** param lists* return*/public ListNode mergeKLists(ListNode[] lists) {if (lists.length 0) {return null;}return split(lists, 0, lists.length-1);}/*** 进行拆分利用分治的思想(类似于快排** param listNodes* param i 左值* param j 右值* return 返回两个链表合并的结果*/public static ListNode split(ListNode[] listNodes, int i, int j) {if(i j){return listNodes[i];}int t (i j) / 2; //中间值ListNode left split(listNodes,i,t);ListNode right split(listNodes,t1,j);return mergeTwoLists(left,right);}如果你看到这里并且上手敲了这几道题我相信你对于递归一定有自己的理解了。递归今天就暂时学到这吧“To Iterate is Human, to Recurse, Divine”,你距离God又近了一步。 七、最后的最后——力扣 2698. 求一个整数的惩罚数
自己动手练练吧2698. 求一个整数的惩罚数 这个题比较难多动手画一下递归过程。 public int punishmentNumber(int n) {int sum 0;for (int i 1; i n; i) {if (check(i * i, i)) {sum i * i;}}return sum;}public boolean check(int n, int i) {if (n i) {return true;}int k 10;/*** 判断数据是否可以进行拆分可以拆分的条件为数字应该大于10并且拆分后的尾数应该小于基准数* 例如121与11,可以拆分为1和21此时nk符合条件* 但是n%k 21,大于11,不可能出现这样的情况符合条件*/while (n k n % k i) {/*将拆分后的数据进行比较例如121拆分为12与1此时n/10 12,n%k 1。得到i-(n%k) 11判断出12 1 ! i*/if (check(n / k, i - (n % k))) {return true;}//依次从个位百位....开始拆分。//例如121,第一次拆分为1,21;第二次为12,1k * 10;}return false;}
