【Java】递归算法

冷不防 2023-09-26 11:48 125阅读 0赞

### 文章目录 ###

*  什么是递归？
 *  递归求阶乘
 *  递归求解斐波那契数列
 *  猴子吃桃问题

--------------------

# 什么是递归？ #

程序 **调用自身** 的编程技巧成为 **递归（recursion）**。

递归算法是一种直接或间接调用、定义自身的函数或方法的算法，也就是调用自身。

递归的实质：将原问题不断分解为规模缩小的子问题，然后用递归调用的方法来表示问题的解；

递归，顾名思义就是 **递 和 归 的过程**：

*  递：将原问题分解为若干个子问题，这些子问题的解决思路相同；
 *  归：当问题不断递进，需要一个明确结束的递归出口（临界点）；

![在这里插入图片描述][130f44e86cf04140ab73bec6b43b56f0.png]  
递归算法是一种自下而上的思维，难点在于逻辑性；

需要明确以下几点：

*  明确递归的终止条件（递归出口）；
 *  明确反复执行的递归过程，如何把若干的子问题联系在一起；
 *  给出递归终止时的处理办法；

下面用几个例子来说明：

# 递归求阶乘 #

![在这里插入图片描述][33536aab6bce4cfaabbe8d5c4ff7f23e.png]

*  这里的递归出口为 0！=1 即 n=0 时 ==1；
 *  递归式子为 n ! = n \* ( n - 1 )

用Java写一个递归函数：

public static int recursion(int n){
        
         if(n==0){
          //递归终止的条件
             return 1;
         }
         return n*recursion(n-1); //递归过程
    }

public class Demo01 {
        
        public static void main(String[] args) {
        
            int rec;//递归
            int num;//普通
            rec=recursion(5);
            num=fun(5);
            System.out.println("用递归算法得到："+rec);
            System.out.println("常规循环得到"+num);
    
    
        }
        //递归实现
        static int recursion(int n){
        
            if(n==0){
          //递归终止的条件
                return 1;
            }
            return n*recursion(n-1); //递归过程
        }
        //非递归实现
        static int fun(int n){
        
            int result=1;
            while(n>1){
        
                result *= n;
                n--;
            }
            return result;
        }
    }

![在这里插入图片描述][c46d2cd830224d86918c3dc47c482248.png]

# 递归求解斐波那契数列 #

斐波那契数列：又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13…  
在数学上，斐波那契数列有如下以递归形式定义：  
 F 0 = 0 , F 1 = 1 F\_0=0 ,F\_1=1 F0=0,F1=1  
 F n = F ( n − 1 ) + F ( n − 2 ) ( n > = 2 , n ∈ N ∗ ) Fn=F(n-1)+F(n-2) \\qquad(n>=2,n\\in N\* ) Fn=F(n−1)\+F(n−2)(n>=2,n∈N∗)  
 F n = \{ 0 n = 0 1 n = 1 F n − 1 + F n − 2 n = 2 , 3 , 4 , 5... ( n 为正整数 ) F\_n=\\begin\{cases\} 0 & n=0 \\\\ 1 & n=1 \\\\ F\_\{n-1\}+F\_\{n-2\} & n=2,3,4,5...(n为正整数) \\end\{cases\} Fn=⎩⎨⎧01Fn−1\+Fn−2n=0n=1n=2,3,4,5...(n为正整数)

*  终止条件（递归出口）为 n-1=1 n-2=0 即 n=1或n=2
 *  递归体即 Fn=F(n-1)+F(n-2)

public static int fibonacci(int n){
        
    	if(n==1 || n==2){
        
    	return 1;
    	}
    	return fibonacci(n-1)+fibonacci(n-2);
    }

或：

*  终止条件 为 n=0 或 n=1 （因为给出了F0和F1的值）;
 *  递归体仍为 Fn=F(n-1)+F(n-2)

public static int fibonacci(int n){
        
        if(n==0){
        
            return 0;
        }else if(n==1){
        
            return 1;
        }
        return fibonacci(n-1)+fibonacci(n-2);
    }

# 猴子吃桃问题 #

![在这里插入图片描述][cb4d2e8ad6d14fad8efbfceb717ed764.png]

> ![在这里插入图片描述][33007d22a3b84244b0b5fa9c66e1384b.png]

![在这里插入图片描述][69d96c8601bf44ba8f94c221c1db9c32.png]

/*  猴子吃桃问题：小猴子摘了一堆桃子。第一天吃掉一半又多吃了1个，第二天吃了剩下的一半又多吃1个，以后每天都吃掉剩下的一半多一个。第10天发现只剩一个桃子了。问第一天摘了多少桃子？第二天还有多少桃子？第三天……
    编写方法peach(int day)，计算第day天的桃子数。
    在main()方法中输入day（1~10），即你想知道第day天小猴子有多少桃子，调用peach()方法求该天的桃子数。
    */
    import java.util.Scanner;
    public class Peach {
        
    
    	public static void main(String[] args) {
        
    		System.out.println("你想知道小猴子第几天的桃子数？请输入（1~10）");
    		Scanner sc = new Scanner(System.in);
    		int day;
    		day = sc.nextInt();
    		System.out.printf("第%d天的桃子数是%d\n",day,peach(day));
    		sc.close();
    	}
    
    	//计算第day天的桃子数
    	static int peach(int day) {
        
    		int n;   //n表示第day天的桃子数
    		
            if(day==10){
        
                return 1;
            }
            return 2*(peach(day+1)+1); 
    	}
    }

[130f44e86cf04140ab73bec6b43b56f0.png]: https://img-blog.csdnimg.cn/130f44e86cf04140ab73bec6b43b56f0.png
[33536aab6bce4cfaabbe8d5c4ff7f23e.png]: https://img-blog.csdnimg.cn/33536aab6bce4cfaabbe8d5c4ff7f23e.png
[c46d2cd830224d86918c3dc47c482248.png]: https://img-blog.csdnimg.cn/c46d2cd830224d86918c3dc47c482248.png
[cb4d2e8ad6d14fad8efbfceb717ed764.png]: https://img-blog.csdnimg.cn/cb4d2e8ad6d14fad8efbfceb717ed764.png
[33007d22a3b84244b0b5fa9c66e1384b.png]: https://img-blog.csdnimg.cn/33007d22a3b84244b0b5fa9c66e1384b.png
[69d96c8601bf44ba8f94c221c1db9c32.png]: https://img-blog.csdnimg.cn/69d96c8601bf44ba8f94c221c1db9c32.png