递归算法——阶乘、斐波那契数列

蔚落 2022-10-28 14:28 217阅读 0赞

### 文章目录 ###

*  前言
 *  一、什么是递归算法？
 *  二、递归算法特点
 *  三、递归算法的使用要求
 *  四、应用示例——阶乘
 *   *  1.阶乘概述
     *  2.思路分析
     *  3.代码实现
 *  五、应用示例——斐波那契数列
 *   *  1.思路分析
     *  2.代码实现
 *  注意

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

# 前言 #

在最近的学习中，我自己感觉我一开始最不理解的就是一个方法里面还可以调用这个方法自己，感觉太不可思议了，今天我们就分享一下这种算法——递归算法

# 一、什么是递归算法？ #

递归是计算机科学的一个重要概念。递归算法就是把问题转化为规模缩小了的同类问题的子问题，然后递归调用函数来表示问题的解。**一个函数直接或间接调用自己本身，这种函数叫递归函数。**

# 二、递归算法特点 #

1、递归就是在过程或函数里调用自己  
2、在使用递归时，必须有一个明确的递归结束条件，称为递归出口  
3、递归算法在算法中的运用一般都看着比较简单，但是运行效率较低，在程序中不提倡使用递归算法设计程序  
4、在递归调用的过程中系统为每一层的返回点、局部变量等其他变量都开辟了栈来储存。递归次数过多容易导致栈溢出，所以不提倡

# 三、递归算法的使用要求 #

递归算法所体现的“重复”一般有三个要求：  
1、每次调用在规模上缩小（通常是减半）  
2、相邻两次重复之间有紧密的联系，前一次要为后一次做准备（即前一次的输出作为后一次的输入）  
3、在问题的规模极小时，必须直接给出解答，否则就会陷入死循环

# 四、应用示例——阶乘 #

## 1.阶乘概述 ##

对于任何正整数N，N!（读作N的阶乘）的值定义为1-N（包括N）的所有整数的阶乘积。那么整数N的阶乘N！可以表示为：  
1！ = 1  
N！ = N \* (N-1)! N>1

## 2.思路分析 ##

1、递归过程实际上就是自身调用自身，它在调用的时候栈是逐步累积的  
2、递归工程应该是一个收敛的过程，即规模逐步缩小，直至可以计算出一个结果

## 3.代码实现 ##

我以输出5的阶乘作为演示  
代码如下（示例）：

public class Factorial { 
    
    	public static void main(String[] args) { 
    		int factorial = factorial(5); // 调用factorial()递归方法，且接收这个方法的返回值
    		System.out.println(factorial);
    	}
    	public static int factorial(int num) {  // 定义一个带参数的阶乘方法，且有返回值
    		int result = 0; // 定义一个变量储存后续的返回值
    		if(num>=0) {  // 先对输出的int类型的整数进行判断，增强代码的健壮性
    			if(num == 1||num == 0) {  // 如果输入的num等于0或1，则返回1（这就是我上面提到的递归出口）
    				result = 1;
    			}else { 
    				result = num*factorial(num-1); //方法调用自己。做递归运算
    			}
    			
    		}else { 
    			System.out.println("请输出大于等于0的整数");
    		}
    		return result;
    	}
    }

代码如下（输出）：

120

# 五、应用示例——斐波那契数列 #

## 1.思路分析 ##

这是一个经典的问题，斐波那契数列是这样定义的：  
f（0） = 0  
f（1） = 1  
当n>1时  
f（n） = f（n-1）+f（n-2）  
斐波那契数列：0,1,1,2,3,5,8,13,21,34,55,89  
1、对于当n>2,求f（n）只需求出f（n-1）和f（n-2），也就是规模为n的问题，慢慢的变成更小规模的问题了  
2、当n = 0或当 n = 1，存在最简单的情景（递归出口）：f（0） = 0， f（1） = 1

## 2.代码实现 ##

输出第五项菲波那切数列的值为例  
代码如下（示例）：

public class Fibonacci { 
    
    	public static void main(String[] args) { 
    		int fibonacci = fibonacci(5); // 调用fibonacci()递归方法，且接收这个方法的返回值
    		System.out.println(fibonacci);
    
    	}
    	public static int fibonacci(int num) {  // 定义一个带参数的方法，且有返回值
    		int result = 0; // 定义一个变量储存后续的返回值
    		if(num>=0) {  // 先对输出的int类型的整数进行判断，增强代码的健壮性
    			if(num == 0) {  // 如果输入的num等于0，则返回0（这就是我上面提到的递归出口）
    				result = 0;
    			}else if(num == 1) { // 如果输入的num等于1，则返回1（这就是我上面提到的递归出口）
    				result = 1;
    			}else { 
    				result = fibonacci(num-1)+fibonacci(num-2);//每缩小一次范围调用自己两次
    			}	
    		}else { 
    			System.out.println("请输入你想要知道的斐波那契数列的第几项（需要大于等于0）");
    		}
    		return result;
    	}
    
    }

代码如下（输出）：

# 注意 #

在编写递归调用函数的时候，一定要把对简单情景的判断写在最前面，以保证函数调用在检查到简单情景的时候能够及时的终止递归，否则的话会陷入死循环