一般定義
程序調用自身的編程技巧稱為遞歸（ recursion）。
一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。遞歸的能力在于用有限的語句來定義對象的無限集合。一般來說，遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。
注意：
(1) 遞歸就是在過程或函數里調用自身；
(2) 在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。
C#遞歸算法實例：
計算數組{1,1,2,3,5,8.......} 第30位值，不用遞歸，我寫出了以下這樣的代碼：
static void Main(string[] args)
...{
int[] num=new int[30];
num[0]=1;
num[1]=1;
int first=num[0];
int second=num[1];
for (int i = 2; i < num.Length; i++)
...{
num[i] = first + second;
first = second;
second = num[i];
}
Console.WriteLine(num[29]);
Console.ReadLine();
}
C#遞歸算法的使用，以下是代碼：
static void Main(string[] args)
...{
Console.WriteLine(Process1(30));
Console.ReadLine();
}
public static int Process1(int i)
...{
//計算數組{1,1,2,3,5,8.......} 第30位值
if (i == 0) return 0;
if (i == 1) return 1;
else
return Process1(i - 1) + Process1(i - 2);
}
// 階乘
public class Factorial {
public static void main(String[] args) {
System.out.println(factorial(6));
}
public static int factorial(int n) {
// 出口點
if (1==n) {
return 1;
} else {
return n * factorial(n - 1);
}
}
}
// 斐波那契數列
public class Fibonacci {
public static void main(String[] args) {
System.out.println(fibonacci(6));
}
// 斐波那契數列：(從第三項開始,后一項都是前兩項的和)
// 1 1 2 3 5 8 13 ......
public static int fibonacci(int n) {
// 出口點
if (1==n || 2==n) {
return 1;
} else {
return fibonacci(n-1) + fibonacci(n-2);
}
}
}
// 遍歷一個目錄下的所有文件
public class FileList {
private static List<String> fileNameList = new ArrayList<String>();
public static void main(String[] args) {
String dir = "D://360Rec";
File file = new File(dir);
addAll(file);
for (String name : fileNameList) {
System.out.println(name);
}
}
public static void addAll(File file) {
// 出口點: 是文件或者是空目錄
if (file.isFile() || file.list().length==0) {
fileNameList.add(file.getName());
} else {
File [] files = file.listFiles();
for (File f : files) {
addAll(f);
if (f.isDirectory() && f.list().length!=0) {
fileNameList.add(f.getName());
}
}
}
}
}
