深入理解递归

﹏ヽ暗。殇╰゛Y 2022-03-18 13:56 198阅读 0赞

**递归的基本思想：以此类推**

**具体来说就是把规模大的问题转换为规模小的相似的子问题来解决，因为解决大问题的方法和解决小问题的方法往往是同一个方法，因此产生函数调用它本身的情况。而且解决该问题的函数必须有结束条件，要不然会无限递归。**

**递归例子:**

**1.阶乘**

public class Main{
    	
    	public static void main(String[] args) {
    	System.out.println(factorial(6));
    	}
    
    	private static int factorial(int n) {
    		// TODO 自动生成的方法存根
    		if(n==1||n==0) {
    			return 1;
    		}else {
    			return n*factorial(n-1);
    		}
    	}
    
    	
    	
    }

**求解6的阶乘时，递归过程如下:**

**![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0haUEhZVA_size_16_color_FFFFFF_t_70][]**

**我们会发现这个过程和栈的工作原理一致，递归调用就是通过栈这种数据结构实现，递就是“入栈”，归就是“出栈”。**

**2.模拟“递”和“归”**

public class Main{
    	
    	public static void main(String[] args) {
    		recursion_display(5);
    	}
    
    	private static void recursion_display(int n) {
    		int t=n;
    		// TODO 自动生成的方法存根
    		System.out.println("递:"+t);
    		if(n>0) {
    		recursion_display(--n);
    		}
    		System.out.println("归:"+t);
    	}
    
    	
    	
    }

递:5
    递:4
    递:3
    递:2
    递:1
    递:0
    归:0
    归:1
    归:2
    归:3
    归:4
    归:5

**3.斐波那契数列**

**公式：Fib(0)=1,Fib(1)=1,Fib(n)=Fib(n-1)+Fib(n-2).**

**1,1,2,3,5,8,13,21……**

public class Main {
    
    	public static void main(String[] args) {
    		fib(5);
    	}
    
    	private static int fib(int n) {
    		if (n == 1 || n == 0) {
    			return 1;
    		} else {
    			return fib(n - 2) + fib(n - 1);
    		}
    		// TODO 自动生成的方法存根
    	}
    
    }

**递归的过程就像树一样，通过观察会发现很多重复的调用。**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0haUEhZVA_size_16_color_FFFFFF_t_70]: /images/20220318/2242386fdae6421fa17e2dcfd4165c95.png