前言

在最近的學(xué)習(xí)中，我自己感覺我一開始最不理解的就是一個(gè)方法里面還可以調(diào)用這個(gè)方法自己，感覺太不可思議了，今天我們就分享一下這種算法——遞歸算法

一、什么是遞歸算法？

遞歸是計(jì)算機(jī)科學(xué)的一個(gè)重要概念。遞歸算法就是把問題轉(zhuǎn)化為規(guī)?？s小了的同類問題的子問題，然后遞歸調(diào)用函數(shù)來表示問題的解。一個(gè)函數(shù)直接或間接調(diào)用自己本身，這種函數(shù)叫遞歸函數(shù)。

二、遞歸算法特點(diǎn)

1、遞歸就是在過程或函數(shù)里調(diào)用自己
2、在使用遞歸時(shí)，必須有一個(gè)明確的遞歸結(jié)束條件，稱為遞歸出口
3、遞歸算法在算法中的運(yùn)用一般都看著比較簡(jiǎn)單，但是運(yùn)行效率較低，在程序中不提倡使用遞歸算法設(shè)計(jì)程序
4、在遞歸調(diào)用的過程中系統(tǒng)為每一層的返回點(diǎn)、局部變量等其他變量都開辟了棧來儲(chǔ)存。遞歸次數(shù)過多容易導(dǎo)致棧溢出，所以不提倡

三、遞歸算法的使用要求

遞歸算法所體現(xiàn)的“重復(fù)”一般有三個(gè)要求：
1、每次調(diào)用在規(guī)模上縮小（通常是減半）
2、相鄰兩次重復(fù)之間有緊密的聯(lián)系，前一次要為后一次做準(zhǔn)備（即前一次的輸出作為后一次的輸入）
3、在問題的規(guī)模極小時(shí)，必須直接給出解答，否則就會(huì)陷入死循環(huán)

四、應(yīng)用示例——階乘

1.階乘概述

對(duì)于任何正整數(shù)N，N!（讀作N的階乘）的值定義為1-N（包括N）的所有整數(shù)的階乘積。那么整數(shù)N的階乘N！可以表示為：
1！ = 1
N！ = N * (N-1)! N>1

2.思路分析

1、遞歸過程實(shí)際上就是自身調(diào)用自身，它在調(diào)用的時(shí)候棧是逐步累積的
2、遞歸工程應(yīng)該是一個(gè)收斂的過程，即規(guī)模逐步縮小，直至可以計(jì)算出一個(gè)結(jié)果

3.代碼實(shí)現(xiàn)

我以輸出5的階乘作為演示
代碼如下（示例）：

public class Factorial {

	public static void main(String[] args) {
		int factorial = factorial(5); // 調(diào)用factorial()遞歸方法，且接收這個(gè)方法的返回值
		System.out.println(factorial);
	}
	public static int factorial(int num) { // 定義一個(gè)帶參數(shù)的階乘方法，且有返回值
		int result = 0; // 定義一個(gè)變量?jī)?chǔ)存后續(xù)的返回值
		if(num>=0) { // 先對(duì)輸出的int類型的整數(shù)進(jìn)行判斷，增強(qiáng)代碼的健壯性
			if(num == 1||num == 0) { // 如果輸入的num等于0或1，則返回1（這就是我上面提到的遞歸出口）
				result = 1;
			}else {
				result = num*factorial(num-1); //方法調(diào)用自己。做遞歸運(yùn)算
			}
			
		}else {
			System.out.println("請(qǐng)輸出大于等于0的整數(shù)");
		}
		return result;
	}
}

代碼如下（輸出）：

五、應(yīng)用示例——斐波那契數(shù)列

1.思路分析

這是一個(gè)經(jīng)典的問題，斐波那契數(shù)列是這樣定義的：
f（0） = 0
f（1） = 1
當(dāng)n>1時(shí)
f（n） = f（n-1）+f（n-2）
斐波那契數(shù)列：0,1,1,2,3,5,8,13,21,34,55,89
1、對(duì)于當(dāng)n>2,求f（n）只需求出f（n-1）和f（n-2），也就是規(guī)模為n的問題，慢慢的變成更小規(guī)模的問題了
2、當(dāng)n = 0或當(dāng) n = 1，存在最簡(jiǎn)單的情景（遞歸出口）：f（0） = 0， f（1） = 1

2.代碼實(shí)現(xiàn)

輸出第五項(xiàng)菲波那切數(shù)列的值為例
代碼如下（示例）：

public class Fibonacci {

	public static void main(String[] args) {
		int fibonacci = fibonacci(5); // 調(diào)用fibonacci()遞歸方法，且接收這個(gè)方法的返回值
		System.out.println(fibonacci);

	}
	public static int fibonacci(int num) { // 定義一個(gè)帶參數(shù)的方法，且有返回值
		int result = 0; // 定義一個(gè)變量?jī)?chǔ)存后續(xù)的返回值
		if(num>=0) { // 先對(duì)輸出的int類型的整數(shù)進(jìn)行判斷，增強(qiáng)代碼的健壯性
			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);//每縮小一次范圍調(diào)用自己兩次
			}	
		}else {
			System.out.println("請(qǐng)輸入你想要知道的斐波那契數(shù)列的第幾項(xiàng)（需要大于等于0）");
		}
		return result;
	}

}

代碼如下（輸出）：