今天我們主要總結一下C#面試中常見遞迴演演算法。
一個正整數的階乘（factorial）是所有小於及等於該數的正整數的積，並且0的階乘為1。自然數n的階乘寫作n!。1808年，基斯頓·卡曼引進這個表示法。
原理：亦即n!=1×2×3×...×(n-1)×n。階乘亦可以遞迴方式定義：0!=1，n!=(n-1)!×n。
/// <summary>
/// C#遞迴演演算法計算階乘的方法
/// 一個正整數的階乘（factorial）是所有小於及等於該數的正整數的積，並且0的階乘為1。自然數n的階乘寫作n!。1808年，基斯頓·卡曼引進這個表示法。
/// 亦即n!=1×2×3×...×(n-1)×n。階乘亦可以遞迴方式定義：0!=1，n!=(n-1)!×n。
/// 最終輸出結果：120
/// </summary>
public static void RecursiveFactorial()
{
int result = Factorial(5);
Console.WriteLine("5的階乘為：" + result);//5!=120
}
public static int Factorial(int n)
{
if (n == 0 || n == 1)
{
return 1;
}
else
{
// 遞迴呼叫：當前數n乘以前面所有數的階乘
return n * Factorial(n - 1);
}
}
/// <summary>
/// 遞迴演演算法陣列求
/// 最終輸出結果為：259
/// </summary>
public static void RecursiveArraySum()
{
int[] numbers = { 1, 88, 66, 4, 100 };
int sum = ArraySum(numbers, 0);
Console.WriteLine("陣列元素的總和為：" + sum);
}
/// <summary>
/// 計算陣列元素的總和
/// </summary>
/// <param name="arr">arr</param>
/// <param name="index">index</param>
/// <returns></returns>
public static int ArraySum(int[] arr, int index)
{
if (index >= arr.Length)
{
// 基本情況：陣列為空或者已經遍歷完所有元素
return 0;
}
else
{
// 遞迴呼叫：當前元素加上剩餘元素的總和
return arr[index] + ArraySum(arr, index + 1);
}
}
一列數的規則如下 : 1 、 1 、 2 、 3 、 5 、 8 、 13 、 21 、 34… 求第 30 位數是多少， 用遞迴演演算法實現。
/// <summary>
/// 使用遞迴演演算法來實現求解斐波納契數列中第30位數的值
/// 一列數的規則如下 : 1 、 1 、 2 、 3 、 5 、 8 、 13 、 21 、 34… 求第 30 位數是多少， 用遞迴演演算法實現
/// 最終輸出結果為：832040
/// </summary>
public static void FibonacciSum()
{
int n = 30;
int result = Fibonacci(n);
Console.WriteLine("第 " + n + "位斐波那契數是：" + result);
}
public static int Fibonacci(int n)
{
if (n <= 0)
{
return 0;
}
else if (n > 0 && n <= 2)
{
return 1;
}
else
{
// 遞迴情況：呼叫自身計算前兩個數位之和
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
}
/// <summary>
/// 使用C#語言編寫的遞迴演演算法來計算1+2+3+4+…+100的結果
/// 最終輸出結果是：5050
/// </summary>
public static void RecursiveAlgorithmSum()
{
int result = SumNumbers(100);
Console.WriteLine("1+2+3+4+...+100 = " + result);
}
public static int SumNumbers(int n)
{
if (n == 1)
{
return 1;//遞迴結束條件
}
else
{
return n + SumNumbers(n - 1);
}
}