什麼是遞迴？ 遞迴的流行解釋是什麼

遞迴，即在奔跑的過程中稱呼自己。 構成遞迴的條件：1

子問題必須與原始問題相同，並且更簡單; 2.它不能無限期地呼叫，必須有乙個出口，簡化為非遞迴條件處理。 在數學和電腦科學中。

，遞迴是指由簡單基本情況（或多種情況）定義的一類物件或方法，並規定所有其他情況都可以簡化為它們的基本情況。 例如，以下是某人祖先的遞迴定義：乙個人的父母是他的祖先（基本情況）。

某人的祖先的父母也是某人的祖先（遞迴步驟）。 斐波那契數列，也稱為分裂數列。

指的是這樣一連串的數字......i[1] 斐波那契數列是遞迴的乙個經典案例：遞迴關係是指乙個實體與自身建立關係。

fib（0） = 1 [基本情況] fib（1） = 1 [基本情況] 整數 > 1 對於所有 n： fib（n） = （fib（n-1） + fib（n-2）） 遞迴定義] 儘管有許多數學函式。

可以遞迴表示，但在實踐中，遞迴定義的高開銷往往令人望而卻步。 例如：階乘。

1） = 1 [基本情況] 所有 n > 1 的整數： factorial（n） = （n * factorial（n-1）） 遞迴定義] 乙個易於理解的心智模型，它認為物件的遞迴定義是根據同類的“先前定義的”物件來定義的。例如：

你怎麼能移動100個箱子？ 答：你首先移動乙個盒子，記下它移動到的位置，然後繼續討論較小的問題：

你怎麼能移動 99 個箱子？ 最終，你的問題將變成如何移動乙個箱子，你已經知道該怎麼做了。 這樣的定義在數學中很常見。

例如，集合論。

自然數的正式定義是：1是自然數，每個自然數都有乙個後繼者，也是自然數。 <>

例如，如果你得到一把鑰匙，你站在門前，問你可以用這把鑰匙開啟多少扇門。 遞迴：你開啟面前的門，看到房子裡還有另一扇門（這扇門可能和你面前開啟的門一樣大（靜態），或者門可能更小（移動）），你走過去，發現你手中的鑰匙還能開啟它， 你推開門，發現裡面還有另一扇門，你繼續開啟它。

幾次後，你開啟面前的一扇門，發現只有乙個房間，而且沒有門。 你開始回到你來時的路，每次你回到乙個房間，你數一數，當你到達入口時，你可以知道你用這把鑰匙開啟了多少扇門。 圈：

你開啟面前的門，你看到房子裡還有另一扇門，（這扇門可能和你面前開啟的門一樣大（靜態），也可能更小（移動）），你走過去發現你手中的鑰匙還能開啟它， 你推開門，發現裡面還有另一扇門，（如果前門是一樣的，這扇門也是一樣的，如果第二扇門比第一扇門小，這扇門也比第二扇門小（同樣的動作，要麼沒有變化，要麼變化一樣））， 你繼續開門。繼續這樣下去。 入口處的人從不等你回去告訴他答案。

呼叫自己的程式設計技術的程式稱為遞迴。 遞迴作為一種演算法在程式語言它被廣泛使用。

乙個過程或函式在其定義或描述中有乙個直接或間接呼叫自身的方法，它通常將乙個大而複雜的問題轉化為乙個類似於原始問題要解決的小問題，遞迴策略可以只用少量程式來描述求解過程。

所需的重複計算次數大大減少了程式的數量。

遞迴的力量在於在有限語句中定義無限的物件集。

一般來說，遞迴需要有邊界條件。

遞迴前向段和遞迴返回段。 當邊界條件不滿足時，遞迴推進; 當滿足邊界條件時，遞迴返回。

遞迴的缺點：

遞迴演算法。 相對常用的演算法，如普通迴圈，效率較低。 因此，應避免遞迴，除非沒有更好的演算法或在遞迴更合適的特定情況下。

在遞迴呼叫過程中，系統為每一層的返回點、本地數量等開啟乙個堆疊來儲存。 過多的遞迴很容易導致堆疊溢位等。

以上內容參考：百科全書 - 遞迴。

1. 遞迴演算法概念：

在函式或子例程中，直接或間接呼叫自己的演算法。

二、基本資訊：

遞迴演算法是乙個子問題，它將乙個問題轉換為乙個較小的同類問題。 然後以遞迴方式呼叫函式或過程來表示問題的解決方案。 直接或間接呼叫自身的過程或函式稱為遞迴過程或函式。

遞迴和迭代都是迴圈的型別。

簡單地說，遞迴就是函式本身的重複呼叫來實現迴圈。 迭代與普通迴圈的區別在於，在迴圈中參與操作的變數也是儲存結果的變數，當前儲存的結果作為下乙個迴圈計算的初始值。

在遞迴迴圈中，當滿足終止條件時，它會逐層返回到末尾。 迭代使用計數器來結束迴圈。 當然，在許多情況下，它是一種多迴圈混合物，具體取決於具體需求。

遞迴的乙個例子是，給定乙個整數陣列，使用減半查詢返回陣列中指定值的索引，假設陣列是排序的，並且為了描述，假設元素都是正數，陣列的長度是 2 的整數倍。

半拆分查詢是一種查詢型別，比遍歷所有元素要快得多。

int find(int *ary,int index,int len,int value)

if（len==1） 最後乙個元素。

if (ary[index]==value)return index;成功的查詢將返回乙個索引。

return -1;失敗，返回 -1

如果長度大於 1，則執行半倍遞迴查詢。

int half=len/2;

檢查選中的值是否大於上半部分的最後乙個值，如果大於，則遞迴查詢後半部分。

if(value>ary[index+half-1])

return find(ary,index+half,half,value);

否則，以遞迴方式查詢上半部分。

return find(ary,index,half,value);

迭代的經典例子是實數的累加，例如從 1 到 100 的所有實數之和。

int v=1;

for(i=2;i<=100;i++)

v=v+i;

遞迴是一種通過反覆將問題分解為同類子問題來解決問題的方法。 遞迴方法可以用來求解多伏特的電腦科學問題，因此它是電腦科學中的乙個重要概念。

絕大多數程式語言都支援函式的自呼叫，其中函式可以通過呼叫自身來遞迴呼叫。 計算理論可以證明遞迴可以完全取代迴圈，因此在許多函式式程式語言中習慣性地使用遞迴來實現迴圈。 在支援自呼叫的程式語言中，遞迴可以通過簡單的函式呼叫來完成。

尾遞迴是指遞迴函式呼叫自身並傳回其值而不向其新增操作。 尾遞迴等同於迴圈，在某些語言中可以優化為迴圈指令。 因此，尾遞迴不會占用這些語言中的呼叫堆疊空間。