遞迴型別

得分: 3.7/5 (44 票)

簡介

在此，我將詳細介紹 C++ 中的遞迴。定義：遞迴是函式呼叫自身的過程，但由於函式呼叫會無限次地進行，因此堆疊幀會超出限制。所以遞迴必須有終止條件。

許多複雜的問題可以透過遞迴用簡單的程式碼來解決。但它比迭代要昂貴得多。因為每次遞迴呼叫都會形成一個堆疊幀。你們都已經知道它的成本了。但是，如果問題非常複雜，除了遞迴之外別無他法。

背景

遞迴首先出現在數學中，然後進入計算機科學。它的使用思想是首先將問題分解為子問題，然後使用遞迴來解決它。

程式碼

在 C++ 中，遞迴可分為兩類
(a) 執行時遞迴: 與 C 中的普通遞迴相同
(b) 編譯時遞迴: 透過使用模板

這些都可以進一步細分為以下幾類

1. 線性遞迴
2. 遞迴
3. 尾部遞迴
4. 相互遞迴
5. 巢狀遞迴

1. 線性遞迴: 這是最常用的遞迴。在此遞迴中，函式以簡單的方式呼叫自身，並透過終止條件終止。這個過程稱為“纏繞”（Winding），當它返回呼叫者時，稱為“解纏”（Un-Winding）。終止條件也稱為基本條件。

示例: 透過線性遞迴計算階乘

執行時版本

程式碼

int Fact(long n)
{
if(0>n)
return -1;
if(0 == n)
return 1;
else
{
return ( n* Fact(n-1));
}
}

纏繞過程

函式呼叫函式返回

Fact(6) 6*Fact(5)
Fact(5) 5*Fact(4)
Fact(4) 4*Fact(3)
Fact(3) 3* Fact(2)
Fact(2) 2* Fact(1)
Fact(1) 1* Fact(0)
終止點
Fact(0) 1

解纏過程

Fact(1) 1*1
Fact(2) 2*1
Fact(3) 3*2*1
Fact(4) 4*3*2*1
Fact(5) 5*4*3*2*1
Fact(6) 6*5*4*3*2*1

編譯時版本

程式碼

// 模板用於基本條件
template <>
struct Fact<0>
{
enum
{
factVal = 1
};
};

template
struct Fact
{
// 透過線性方法進行遞迴呼叫
enum
{
value = n * Fact::factVal
};
};

要測試它在編譯時如何工作，只需呼叫
cout <<>::factVal ;
並編譯它，然後會出現編譯器錯誤，因為沒有針對 -1 的模板。

2. 遞迴: 遞迴是一個函式一次呼叫兩次的過程，而不是一次呼叫一次。它主要用於樹形資料結構，如遍歷、查詢高度、合併等操作。

示例: 斐波那契數列

執行時版本程式碼
程式碼

int FibNum(int n)
{
// 基本條件
if (n < 1)
return -1;
if (1 == n || 2 == n)
return 1; // 透過遞迴方法進行遞迴呼叫
return FibNum(n - 1) + FibNum(n - 2);
// 一次呼叫兩個遞迴函式，所以是遞迴
}
// binary }

編譯時版本程式碼
程式碼

// 基本條件
template<>
struct FibNum<2>
{
enum { val = 1 };
};
template <>
struct FibNum<1>
{
enum { val = 1 };
};

// 透過遞迴方法進行遞迴呼叫
template
struct FibNum
{
enum { val= FibNum::val + FibNum::val };
};

3. 尾部遞迴: 在此方法中，遞迴函式最後被呼叫。因此，它比線性遞迴方法更有效。這意味著終止點將（100%）出現，你只需要設定該條件。

示例: 斐波那契數列

執行時版本程式碼
程式碼

int FibNum(int n, int x, int y)
{
if (1 == n) // 基本條件
{
return y;
}
else // 透過尾部方法進行遞迴呼叫
{
return FibNum(n-1, y, x+y);
}
}

編譯時版本程式碼

程式碼

template
struct FibNum
{
// 透過尾部方法進行遞迴呼叫
enum
{
val = FibNum::val
};
};

// 基本條件或終止
template
struct FibNum<1,>
{
enum
{
val = y
};
};

4. 相互遞迴: 函式相互呼叫。例如，FunA 呼叫 FunB，FunB 又遞迴呼叫 FunA。這實際上不是遞迴，但它做的事情與遞迴相同。所以你可以說，不支援遞迴呼叫的程式語言，可以透過相互遞迴來實現遞迴的需求。基本條件可以應用於一個、多個或所有函式中的任何一個。

示例: 判斷奇偶數

執行時版本程式碼
程式碼

bool IsOddNumber(int n)
{
// 基本或終止條件
if (0 == n)
return 0;
else
// 透過相互方法進行遞迴呼叫
return IsEvenNumber(n - 1);
}
bool IsEvenNumber(int n)
{
// 基本或終止條件
if (0 == n)
return 1;
else
// 透過相互方法進行遞迴呼叫
return IsOddNumber(n - 1);
}

編譯時版本程式碼
程式碼

// 基本或終止條件
template <>
struct IsOddNumber<0>
{
enum
{
val = 0
};
};
template <>
struct IsEvenNumber<0>
{
enum
{
val = 1
};
};

// 透過相互方法進行遞迴呼叫

template
struct IsOddNumber
{
enum
{
val = n == 0 ? 0 : IsEvenNumber::val
};
};

template
struct IsEvenNumber
{
enum
{
val = n == 0 ? 1 : IsOddNumber::val
};
};

5. 巢狀遞迴: 這與其他所有遞迴都非常不同。除了巢狀遞迴，所有遞迴都可以轉換為迭代（迴圈）。你可以透過 Ackermann 函式的例子來理解這種遞迴。

示例: Ackermann 函式

執行時版本程式碼
程式碼

int Ackermann(int x, int y)
{
// 基本或終止條件
if (0 == x)
{
return y + 1;
}
// 錯誤處理條件
if (x <> 0 && 0 == y)
{
return Ackermann(x-1, 1);
}
// 透過巢狀方法進行遞迴呼叫
else
{
return Ackermann(x-1, Ackermann(x, y-1));
}
}

編譯時版本程式碼
程式碼

// 基本或終止條件
template
struct Ackermann<0,>
{
enum { val = y + 1 };
};

// 透過線性方法進行遞迴呼叫
template
struct Ackermann
{
enum
{
val = Ackermann::val
};
};
// 透過巢狀方法進行遞迴呼叫
template
struct Ackermann
{
列舉
{
val = Ackermann ::val>::val
};
};

C++

文章

遞迴型別