9-recursion

9-recursion 2020年12月28日 9:51

	iterate	recursion
优点	速度快，结构简单，效率高	代码更简洁清晰，可读性更好。
缺点	1，不容易 理解 ，编写复杂问题时困难。 2，并不能解决所有的问题	由于递归需要系统堆栈，所以空间消耗要比非递归代码要大很多。而且，如果递归深度太大，可能系统撑不住。

	Iterative	recursion
优点	It has fast speed, simple structure and high efficiency.	The code is cleaner and more readable.
缺点	1. It is not easy to understand and it is difficult to solve complex problems. 2. It cannot solve all the problems	Because recursion requires a system stack, space consumption is much larger than for non-recursive code. Also, if the recursion depth is too deep, the system may not hold.

一、Recursion 1，定义 Recursion is when a method calls itself • The method keeps calling itself until it reaches the base case and then it filters back up

• The characteristics of a recursive method are • It calls itself • When it calls itself, it does so to solve a smaller problem • There’s some version of the problem that is simple enough that the routine can solve it and return without calling itself

2，递归程序必须有base case【让递归结束的判断】，否则程序无法停止

二、案例 1，triangular numbers

	

2，Fibonacci Series 1）The Fibonacci series is as follows: 1, 1, 2, 3, 5, 8, 13…

	public static void test(int n) { int f1=1; int f2=1; int current=0; if(n==1||n==2) { System.out.println(1); return; } for(int i=2;i<n;i++) { current=f1+f2; int temp=f2; f2=current; f1=temp; } System.out.println(current); }

数较小的时候用递归较好，数较大的时候用递归需要等待很久 Lesson: recursion can simplify code but is not always more efficient

Bottom-Up solution for Fibonacci Series	Top-Down recursive approach

2）The efficiency of recursion

2，检查是否回文palindrome

检查是否回文palindrome
public static boolean isPalindrome(String s) { if(s.length()<=1) { return true; }else { char first=s.charAt(0); char last=s.charAt(s.length()-1); if(first!=last) { return false; }else { return isPalindrome(s.substring(1,s.length()-1)); } } }

3，Raising to a power

	In the previous example, the power was always even, so could be easily divided by two • If the power happens to be odd then we need to subtract one from the power, solve that, and then multiply it again to account for the power we subtracted

三、动态规划 dynamic programming 1，Dynamic programming (dynamic optimization) is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions 把大问题分成小问题，让多个重复的小问题不重复解决，将解决过的问题存储起来，直接使用

注意 1. The problem involves overlapping sub-problems that need to be solved again and again. In dynamic programming we solve these sub problems only once and store it for future use

2. If a big problem can be solved by using the solutions of the sub problems then we say that problem also has an optimal substructure property

四、分治算法 Divide and Conquer 1， The big problem is divided into two smaller problems and each one is solved separately These are then divided into even smaller problems etc。The process continues until you get to the base case which can be solved easily with no further division

2，案例

1--Binary Search   private static int binarySearch(int[] arr, int target) { int left=0; int right=arr.length-1; while(left<=right) { int mid=(left+right)/2; if(target==arr[mid]) { return mid; }else if(target<arr[mid]) { right=mid-1; }else { left=mid+1; } } return -1; }
2--汉诺塔Towers of Hanoi 1，问T   古代的做法  2，算法 • Assuming there are n disks, the algorithm is • 1. Move the subtree of the top n-1 disks from source rod to intermediate rod • 2. Move the remaining largest disk from source rod to destination rod • 3. Now solve moving the subtree from intermediate rod to destination rod   
3--Mergesort    1,思路 divide an array in half and sort each half  1）merge • So, if we want to marge any two lists s1 and s2, we need at most s1.length() + s2.length() steps     2)分开   用循环来解   3)Copies and Comparisons  2,分析    

时间复杂度分析