遞歸

1.基礎(chǔ)簡(jiǎn)介

遞歸在計(jì)算機(jī)科學(xué)中，遞歸是一種解決計(jì)算問(wèn)題的方法，其中解決方案取決于同一類問(wèn)題的更小子集

例如 遞歸遍歷環(huán)形鏈表

• 基本情況（Base Case）：基本情況是遞歸函數(shù)中最簡(jiǎn)單的情況，它們通常是遞歸終止的條件。在基本情況下，遞歸函數(shù)會(huì)返回一個(gè)明確的值，而不再進(jìn)行遞歸調(diào)用。
• 遞歸情況（Recursive Case）：遞歸情況是遞歸函數(shù)中描述問(wèn)題規(guī)模較大的情況。在遞歸情況下，函數(shù)會(huì)調(diào)用自身來(lái)解決規(guī)模更小的子問(wèn)題，直到達(dá)到基本情況。

優(yōu)點(diǎn)

1. 簡(jiǎn)潔清晰：遞歸能夠?qū)?fù)雜的問(wèn)題簡(jiǎn)化成更小的子問(wèn)題，使得代碼更加清晰易懂。
2. 問(wèn)題建模：遞歸能夠自然地將問(wèn)題建模成遞歸結(jié)構(gòu)，使得問(wèn)題的解決變得更加直觀。
3. 提高代碼復(fù)用性：通過(guò)遞歸，可以在不同的情景中復(fù)用相同的解決方案。

缺點(diǎn)

1. 性能損耗：遞歸調(diào)用涉及函數(shù)的重復(fù)調(diào)用和堆棧的頻繁使用，可能會(huì)導(dǎo)致性能下降。
2. 內(nèi)存消耗：每次遞歸調(diào)用都需要在堆棧中存儲(chǔ)函數(shù)的調(diào)用信息，可能會(huì)導(dǎo)致堆棧溢出的問(wèn)題。
3. 難以理解和調(diào)試：復(fù)雜的遞歸調(diào)用可能會(huì)導(dǎo)致代碼的難以理解和調(diào)試，特別是遞歸函數(shù)中存在多個(gè)遞歸調(diào)用時(shí)。

常用場(chǎng)景

1. 樹和圖的遍歷：樹和圖的結(jié)構(gòu)天然適合遞歸的處理方式，如深度優(yōu)先搜索（DFS）。
2. 分治算法：許多分治算法，如歸并排序和快速排序，都是通過(guò)遞歸實(shí)現(xiàn)的。
3. 動(dòng)態(tài)規(guī)劃：動(dòng)態(tài)規(guī)劃問(wèn)題中，遞歸可以幫助描述問(wèn)題的遞歸結(jié)構(gòu)，但通常需要使用記憶化搜索或者自底向上的迭代方式來(lái)提高性能。
4. 排列組合問(wèn)題：許多排列組合問(wèn)題，如子集、組合、排列等，可以通過(guò)遞歸實(shí)現(xiàn)。

/**
 * 遞歸進(jìn)行遍歷
 * @param node   下一個(gè)節(jié)點(diǎn)
 * @param before 遍歷前執(zhí)行的方法
 * @param after  遍歷后執(zhí)行的方法
 * @deprecated  遞歸遍歷,不建議使用,遞歸深度過(guò)大會(huì)導(dǎo)致棧溢出。建議使用迭代器,或者循環(huán)遍歷,或者使用尾遞歸,或者使用棧
 * @see #loop(Consumer, Consumer)
 */
public void recursion(Node node, Consumer<Integer> before, Consumer<Integer> after){
    // 表示鏈表沒(méi)有節(jié)點(diǎn)了，那么就退出(注意 環(huán)形鏈表的 末尾 不是null 而是頭節(jié)點(diǎn))
    if (node == sentinel){
        return;
    }
    // 反轉(zhuǎn)位置就是逆序了
    before.accept(node.value);
    recursion(node.next, before, after);
    after.accept(node.value);
}

1. 自己調(diào)用自己，說(shuō)明每一個(gè)函數(shù)對(duì)應(yīng)著一種解決方案，自己調(diào)用自己意味著解決方案是一樣的或者說(shuō)是有規(guī)律的
2. 每次調(diào)用，函數(shù)處理的數(shù)據(jù)相對(duì)于上一次會(huì)縮減，而且最后會(huì)縮減至無(wú)需繼續(xù)遞歸
3. 內(nèi)層函數(shù)調(diào)用（子集處理完成），外層函數(shù)才能調(diào)用完成

1.1.思路

首先需要確定自己的問(wèn)題，能不能用遞歸的思路去解決

然后需要推導(dǎo)出遞歸的關(guān)系，父問(wèn)題和子問(wèn)題之間的關(guān)系， 以及遞歸的中止條件

$$f(n)=\{\begin{array}{ll}停止& ,n=null\\ f(n,next)& ,n\ne null\end{array}$$

1. 深入到最里層的 叫做遞
2. 從最里層出來(lái)的叫做歸
3. 在遞過(guò)程中，外層函數(shù)內(nèi)的局部變量（以及參數(shù)方法）并未消失，歸的時(shí)刻還會(huì)用到。

2.案例

2.1.案例1-求階乘

@Test
@DisplayName("測(cè)試-遞歸-階乘")
public void test1(){
    int factorial = factorial(5);
    logger.error("factorial :{}",factorial);
}


/**
 * 階乘
 * @param value 階乘的值
 * @return 階乘的結(jié)果
 */
public int factorial(int value){
    // 遞歸的終止條件
    if(value ==1){
        return 1;
    }
    // 遞歸的公式 f(n) = n * f(n-1)
    return value * factorial(value-1);
}

2.2.案例2-字符串反轉(zhuǎn)

• 遞：n從0開始，每次都從都頭部對(duì)字符串進(jìn)行分割，每次拼接的字符串只取第一位
• 歸：從 str.length() == 1開始?xì)w，從歸開始拼接，自然是逆序的

# 思路
	遞歸的終止條件是字符串的長(zhǎng)度為1, 遞歸的公式是 f(n) = f(n-1) + str.charAt(0) 從后往前拼接字符串

/**
 * 反向打印字符串序列
 * @param str 字符串
 * @return 反向打印的字符串
 */
public String reverse(String str){
    if(str.length() == 1){
        return str;
    }
    logger.error("str.substring(1) = {} , str.CharArt(0) = {}",str.substring(1),str.charAt(0));
    // substring(1) 從下標(biāo)為1的位置開始截取字符串, chatAt(0) 獲取下標(biāo)為0的字符
    return reverse(str.substring(1)) + str.charAt(0);
}


@Test
@DisplayName("測(cè)試-遞歸-反向打印字符串序列")
public void test2(){
    String str = "abcdefg";

    String reverse = reverse(str);
    logger.error("reverse :{}",reverse);
}

2.3.案例3-遞歸二分查找

	/**
	 * 二分查找
	 * @param source 原始數(shù)組
	 * @param target 目標(biāo)值
	 * @param left 左邊界
	 * @param right 右邊界
	 * @return 目標(biāo)值的索引位置
	 */
	public int binaryFind(int source[],int target,int left,int right){
		// 先找到中間值
		int mid = (left + right) >>> 1;
		if (left > right){
			// 如果left > right 直接返回-1
			return -1;
		}
		if (source[mid] < target){
			// 如果中間值小于目標(biāo)值，則在右邊進(jìn)行尋找
			return binaryFind(source,target,mid+1,right);
		} else if(source[mid] > target){
			// 如果中間值大于目標(biāo)值 則在左邊進(jìn)行尋找
			return binaryFind(source,target,left,mid-1);
		} else {
			// 如果中間值等于目標(biāo)值,則返回索引位置
			return mid;
		}
	}


	/**
	 * 二分查找
	 * @param source 原始數(shù)組
	 * @param target 目標(biāo)值
	 * @return 目標(biāo)值的索引位置
	 */
	public int search(int[] source,int target){
		// 二分查找 遞歸的終止條件是 left > right
		return binaryFind(source,target,0,source.length-1);
	}


	@Test
	@DisplayName("測(cè)試-遞歸-二分查找")
	public void test3(){
		int[] source = {1,2,3,4,5,6,7,8,9,10};
		int target = 3;
		int index = search(source,target);
		logger.error("index :{}",index);
	}

2.4.案例4-遞歸冒泡排序

遞歸冒泡排序原理：

遞歸冒泡排序是一種排序算法，它將數(shù)組分成已排序和未排序兩部分。通過(guò)遞歸地比較相鄰元素并交換它們的位置，每次遞歸都將未排序部分的最大元素移到已排序部分的末尾，直到整個(gè)數(shù)組有序。

實(shí)現(xiàn)思路：

1. 初始化：將整個(gè)數(shù)組視為未排序部分。
2. 遞歸調(diào)用：遞歸地調(diào)用 bubble_sort() 函數(shù)來(lái)處理未排序部分，直到未排序部分長(zhǎng)度為0或1，排序結(jié)束。
3. 比較與交換：在每次遞歸中，從數(shù)組開始處向后遍歷，比較相鄰元素。如果前一個(gè)元素大于后一個(gè)元素，則交換它們的位置。
4. 更新未排序部分：記錄每次交換的位置，即最后一次交換的索引，作為下一次遞歸的邊界，確保下一次遞歸只需處理未排序部分的子數(shù)組。
5. 終止條件：遞歸終止條件是未排序部分長(zhǎng)度為0或1，表示數(shù)組已排序完成。

可優(yōu)化的地方及優(yōu)勢(shì)：

• 優(yōu)化點(diǎn)：遞歸冒泡排序在每次遞歸中，對(duì)未排序部分進(jìn)行了全遍歷，可能導(dǎo)致效率較低，尤其是對(duì)于大型數(shù)組。
• 優(yōu)勢(shì)：遞歸冒泡排序的主要優(yōu)勢(shì)在于其簡(jiǎn)潔易懂的實(shí)現(xiàn)方式，易于理解和實(shí)現(xiàn)。

實(shí)現(xiàn)突出重點(diǎn)：

• 遞歸調(diào)用：通過(guò)遞歸調(diào)用 bubble_sort() 函數(shù)，將排序過(guò)程分解為子問(wèn)題，直到基本情況（未排序部分長(zhǎng)度為0或1）得到解決。
• 邊界更新：每次遞歸后，更新未排序部分的邊界，使下一次遞歸只需處理未排序部分的子數(shù)組。
• 終止條件：設(shè)定遞歸終止條件，確保排序過(guò)程能夠正確結(jié)束。

# 思路
	比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
	對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。
	針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
	持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。
# 控制
	1（遞歸）每次重新劃分排序的區(qū)間，負(fù)責(zé)把已經(jīng)排序的區(qū)間進(jìn)行過(guò)濾
	2（循環(huán)）負(fù)責(zé)兩兩比較交換。

	/**
	 * 遞歸冒泡排序
	 * <ul>
	 *     <li>將數(shù)組劃分成兩部分，[0,j] [j+1,length - 1]</li>
	 *     <li>[0,j] 左邊是未排序的部分</li>
	 *     <li>[j+1,length - 1] 右邊是已經(jīng)排序的部分</li>
	 *     <li>在未排序的區(qū)間內(nèi)，相鄰的兩個(gè)元素比較，如果前一個(gè)元素大于后一個(gè)元素，那么交換位置</li>
	 *
	 * </ul>
	 * @param source
	 */
	public void sort (int [] source){
		bubble_sort(source,source.length-1);

	}

	/**
	 * 遞歸冒泡排序
	 * @param source 待排序的數(shù)組
	 * @param j 未排序的區(qū)間的起始位置
	 */
	public void bubble_sort(int [] source,int j){
		// 遞歸的終止條件是數(shù)組的長(zhǎng)度為1 或者數(shù)組的長(zhǎng)度為0
		if (j == 0){
			return;
		}
		// x充 未排序 和已經(jīng)排序的分界線
		int x = 0;
		// 每次都是從0開始
		for (int i = 0; i < j;i++){
			// 如果前一個(gè)元素比后一個(gè)元素大，那么交換位置
			if (source[i] > source[i+1]){
				int temp = source[i];
				source[i] = source[i+1];
				source[i + 1] = temp;
				x = i;
			}
		}
		// 遞歸調(diào)用(因?yàn)槊看巫畲笾刀紩?huì)移動(dòng)到最后，所以每次的排序區(qū)間都往前進(jìn)行移動(dòng))
		bubble_sort(source,x-1);
	}



	@Test
	@DisplayName("測(cè)試-遞歸-冒泡排序")
	public void test4(){
		int[] source = {4,3,2,1,5,6,7};
		sort(source);
		logger.error("source :{}",source);
	}

2.5.案例5-插入排序

插入排序原理：

插入排序是一種直觀的排序算法，類似于整理?yè)淇伺?。它從未排序的部分選取元素，并將其插入到已排序的序列中，直到所有元素都排好序?yàn)橹埂?/p>

實(shí)現(xiàn)思路：

這段代碼使用遞歸來(lái)實(shí)現(xiàn)插入排序。在遞歸函數(shù) insertion() 中，每次調(diào)用時(shí)，它從未排序的部分選擇第一個(gè)元素 t = source[low]，然后將其插入到已排序的序列中的適當(dāng)位置。

具體實(shí)現(xiàn)過(guò)程如下：

1. 從右向左遍歷已排序的部分，找到第一個(gè)比待插入元素小的位置。
2. 將比待插入元素大的元素往后移一位，為待插入元素騰出空間。
3. 插入待排序元素到找到的位置，插入位置為 i + 1，其中 i 是最后一個(gè)比待插入元素小的元素的下標(biāo)。

遞歸終止條件：

遞歸的終止條件是當(dāng) low 等于數(shù)組長(zhǎng)度時(shí)，表示所有元素都已處理完成，無(wú)需繼續(xù)排序。

/**
 * 插入排序
 * @param source 原始數(shù)組
 */
public void insert_sort(int[]source){
    // 遞歸調(diào)用插入排序 low 從1開始
    insertion(source,1);
}

/**
 * 插入排序
 * @param source 原始數(shù)組
 * @param low 未排序數(shù)據(jù)的起始位置
 */
private void insertion(int[]source,int low){
    // 遞歸的終止條件是 low == source.length
    if(low == source.length){
        return;
    }
    // 存儲(chǔ)臨時(shí)變量 （存放low指向的數(shù)據(jù)）
    int t = source[low];
    // 已經(jīng)排序區(qū)域的指針
    int i = low -1;

    // 從右往左找，只要找到第一個(gè)比t小的就能確認(rèn)插入位置
    while (i >=0 && source[i] > t ){
        // 如果沒(méi)有找到插入位置 一直循環(huán)
        // 空出插入位置
        source[i+1] = source[i];
        i--;
    }
    // 找到了插入位置
    // 將t賦值給i +1 的位置就行了
    source[i + 1]  = t;

    insertion(source,low + 1);

}


@Test
@DisplayName("測(cè)試-遞歸-插入排序")
public void test5(){
    int[] source = {2,4,5,10,7,1};
    insert_sort(source);
    logger.error("source :{}",source);
}

多路遞歸

2.案例1-斐波那契數(shù)列

• 每個(gè)遞歸只包含一個(gè)自身的調(diào)用，稱之為single recursion
• 如果每個(gè)遞歸函數(shù)包含多個(gè)自身的調(diào)用稱為multi recursion

$$f(n)=?\begin{array}{ll}0& ,n=0\\ 1& ,n=1\\ f(n?1)+f(n?2)& ,n>1\end{array}$$

?
?

	@Test
	@DisplayName("測(cè)試-遞歸-斐波那契數(shù)列")
	public void test1(){
		int factorial = factorial(10);
		logger.info("factorial:{}",factorial);
	}


	/**
	 * 斐波那契數(shù)列
	 * @param n 傳入的參數(shù)
	 * @return 返回的結(jié)果
	 */
	public int factorial(int n){
		// 遞歸的出口，當(dāng)n為0時(shí)，返回0，當(dāng)n為1或者2時(shí)，返回
		if (n == 0){
			return 0;
		}
		if (n == 1  || n == 2){
			return 1;
		}
		// 依次往下遞歸
		return factorial(n-1) + factorial(n -2);
	}

遞歸爆棧

1.分析

在Java中，遞歸爆棧是指遞歸調(diào)用導(dǎo)致調(diào)用棧溢出的情況。在解釋遞歸爆棧時(shí)，我們可以涉及到Java的內(nèi)存模型和變量存儲(chǔ)位置的分析。

1.1 Java 內(nèi)存模型：

Java程序在運(yùn)行時(shí)，內(nèi)存被劃分為不同的區(qū)域，其中涉及到：

• 堆（Heap）：用于存儲(chǔ)對(duì)象實(shí)例，由Java垃圾回收器進(jìn)行管理和清理。
• 棧（Stack）：每個(gè)線程都有自己的棧，用于存儲(chǔ)局部變量、方法調(diào)用和部分對(duì)象引用。
• 方法區(qū)（Method Area）：存儲(chǔ)類的結(jié)構(gòu)信息、靜態(tài)變量、常量等。
• 程序計(jì)數(shù)器（Program Counter）：記錄線程執(zhí)行的當(dāng)前位置。

1.2. 遞歸的內(nèi)存分析：

在Java中，每次方法調(diào)用都會(huì)在棧上分配一定的空間，包括方法的參數(shù)、局部變量和返回地址。當(dāng)一個(gè)方法被調(diào)用時(shí)，會(huì)將當(dāng)前方法的上下文（包括參數(shù)、局部變量等）推入棧中，當(dāng)方法執(zhí)行結(jié)束時(shí)，棧頂?shù)膸瑫?huì)被彈出。

1.3. 遞歸爆棧的原因：

遞歸函數(shù)在調(diào)用自身時(shí)，會(huì)持續(xù)地將新的調(diào)用幀推入棧中，如果遞歸調(diào)用的深度過(guò)大，棧空間會(huì)耗盡，導(dǎo)致棧溢出錯(cuò)誤。

1.4. 變量存儲(chǔ)位置分析：

• 局部變量（Local Variables）：在方法執(zhí)行時(shí)，局部變量存儲(chǔ)在棧幀中，并且隨著方法的結(jié)束而被銷毀。
• 實(shí)例變量（Instance Variables）：實(shí)例變量存儲(chǔ)在對(duì)象的堆內(nèi)存中，隨著對(duì)象的創(chuàng)建和銷毀而分配和釋放。
• 靜態(tài)變量（Static Variables）：靜態(tài)變量存儲(chǔ)在方法區(qū)中，它們?cè)陬惣虞d時(shí)被初始化，在程序結(jié)束時(shí)銷毀。

2.代碼

/**
 * 遞歸求和
 * @param n 傳入的參數(shù)
 * @return 返回的結(jié)果
 */
public int add(int n){
    if (n == 1){
        return 1;
    }
    return add(n -1)  + n;
}


@Test
@DisplayName("測(cè)試-遞歸-遞歸求和")
public void test2(){
    int sum = add(11111110);
    logger.error("sum:{}",sum);
}

3.解決

# 目前只有C++ 和 scala 能針對(duì)尾遞歸優(yōu)化，所以我們一般需要將遞歸轉(zhuǎn)為循環(huán)來(lái)寫

• 尾調(diào)用

// 如果函數(shù)的最后一步，是調(diào)用一個(gè)函數(shù)，那么成為尾調(diào)用
function a(){
    return b();
}

// 下面這個(gè) 三段代碼并不能稱為尾調(diào)用
function a(){
    // 雖然調(diào)用了函數(shù)，但是又用到了外層函數(shù)的數(shù)值1
    return b() + 1;
}

function a(){
    // 最后異步并非調(diào)用函數(shù)
    const c = b() + 1
    return c;
}

function a(x){
  // 雖然調(diào)用了函數(shù)，但是又用到了外層函數(shù)的數(shù)值x
    return b() + x;
}

4.總結(jié)

遞歸爆棧的問(wèn)題通常發(fā)生在遞歸調(diào)用的深度過(guò)大時(shí)，導(dǎo)致?？臻g耗盡。通過(guò)合理控制遞歸調(diào)用深度、優(yōu)化算法或者考慮使用迭代等方法可以避免這類問(wèn)題，在Java中，局部變量和方法調(diào)用的棧幀管理是導(dǎo)致遞歸爆棧的關(guān)鍵因素之一。
遞歸是一種強(qiáng)大的問(wèn)題解決工具，能夠簡(jiǎn)化問(wèn)題、提高代碼的清晰度和可讀性。然而，在使用遞歸時(shí)，需要注意避免潛在的性能問(wèn)題和堆棧溢出問(wèn)題。選擇適當(dāng)?shù)膱?chǎng)景和合適的算法，可以充分發(fā)揮遞歸的優(yōu)勢(shì)，提高程序的效率和可維護(hù)性。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-831637.html

到了這里，關(guān)于【遞歸】：原理、應(yīng)用與案例解析 ，助你深入理解遞歸核心思想的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！