一般定義
程序調(diào)用自身的編程技巧稱為遞歸（ recursion）。
一個(gè)過(guò)程或函數(shù)在其定義或說(shuō)明中有直接或間接調(diào)用自身的一種方法，它通常把一個(gè)大型復(fù)雜的問(wèn)題層層轉(zhuǎn)化為一個(gè)與原問(wèn)題相似的規(guī)模較小的問(wèn)題來(lái)求解，遞歸策略只需少量的程序就可描述出解題過(guò)程所需要的多次重復(fù)計(jì)算，大大地減少了程序的代碼量。遞歸的能力在于用有限的語(yǔ)句來(lái)定義對(duì)象的無(wú)限集合。一般來(lái)說(shuō)，遞歸需要有邊界條件、遞歸前進(jìn)段和遞歸返回段。當(dāng)邊界條件不滿足時(shí)，遞歸前進(jìn)；當(dāng)邊界條件滿足時(shí)，遞歸返回。
注意：
(1) 遞歸就是在過(guò)程或函數(shù)里調(diào)用自身；
(2) 在使用遞歸策略時(shí)，必須有一個(gè)明確的遞歸結(jié)束條件，稱為遞歸出口。
C#遞歸算法實(shí)例：
計(jì)算數(shù)組{1,1,2,3,5,8.......} 第30位值，不用遞歸，我寫(xiě)出了以下這樣的代碼：
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)
...{
//計(jì)算數(shù)組{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) {
// 出口點(diǎn)
if (1==n) {
return 1;
} else {
return n * factorial(n - 1);
}
}
}
// 斐波那契數(shù)列
public class Fibonacci {
public static void main(String[] args) {
System.out.println(fibonacci(6));
}
// 斐波那契數(shù)列：(從第三項(xiàng)開(kāi)始,后一項(xiàng)都是前兩項(xiàng)的和)
// 1 1 2 3 5 8 13 ......
public static int fibonacci(int n) {
// 出口點(diǎn)
if (1==n || 2==n) {
return 1;
} else {
return fibonacci(n-1) + fibonacci(n-2);
}
}
}
// 遍歷一個(gè)目錄下的所有文件
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) {
// 出口點(diǎn): 是文件或者是空目錄
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());
}
}
}
}
}
