C# 遞歸函數詳細介紹及使用方法

2024-09-07 17:05:23

字體：大中小

來源：轉載

供稿：網友

什么是遞歸函數/方法？
任何一個方法既可以調用其他方法也可以調用自己，而當這個方法調用自己時，我們就叫它遞歸函數或遞歸方法。

通常遞歸有兩個特點：
1. 遞歸方法一直會調用自己直到某些條件被滿足
2. 遞歸方法會有一些參數，而它會把一些新的參數值傳遞給自己。
那什么是遞歸函數？函數和方法沒有本質區別，但函數僅在類的內部使用。以前C#中只有方法，從.NET 3.5開始才有了匿名函數。

所以，我們最好叫遞歸方法，而非遞歸函數，本文中將統一稱之為遞歸。

在應用程序中為什么要使用遞歸？何時使用遞歸？如何用？
“寫任何一個程序可以用賦值和if-then-else語句表示出來，而while語句則可以用賦值、if-then-else和遞歸表示出來。”（出自Ellis Horowitz的《數據結構基礎（C語言版）》 - Fundamentals of Data Structure in C）
遞歸解決方案對于復雜的開發來說很方便，而且十分強大，但由于頻繁使用調用棧（call stack）可能會引起性能問題（有些時候性能極差）。
我們來看一看下面這個圖：
Proj0

調用棧圖示
下面我打算介紹一些例子來幫助你更好的理解遞歸的風險和回報。
1. 階乘
階乘（!）是小于某個數的所有正整數的乘積。
0! = 1
1! = 1
2! = 2 * 1! = 2
3! = 3 * 2! = 6
...
n! = n * (n - 1)!
下面是計算階乘的一種實現方法（沒有遞歸）：
代碼如下:
public long Factorial(int n)
{
if (n == 0)
return 1;
long value = 1;
for (int i = n; i > 0; i--)
{
value *= i;
}
return value;
}

下面是用遞歸的方法實現計算階乘，與之前的代碼比起來它更簡潔。
代碼如下:
public long Factorial(int n)
{
if (n == 0)//限制條件，對該方法調用自己做了限制
return 1;
return n * Factorial(n - 1);
}

你知道的，n的階乘實際上是n-1的階乘乘以n，且n>0。
它可以表示成 Factorial(n) = Factorial(n-1) * n
這是方法的返回值，但我們需要一個條件
如果 n=0 返回1。
現在這個程式的邏輯應該很清楚了，這樣我們就能夠輕易的理解。

2. Fibonacci數列
Fibonacci數列是按以下順序排列的數字：
0,1,1,2,3,5,8,13,21,34,55,…如果F0 = 0 并且 F1= 1 那么Fn = Fn-1 + Fn-2
下面的方法就是用來計算Fn的（沒有遞歸，性能好）
代碼如下:
public long Fib(int n)
{
if (n < 2)
return n;
long[] f = new long[n+1];
f[0] = 0;
f[1] = 1;

上一篇：C#時間格式化(Datetime)用法詳解

下一篇：C# SetCursorPos簡介及使用說明