快捷導(dǎo)航

遞歸案例分享

更新時間：2014年05月19日 15:13:53 作者：

一般定義：程序調(diào)用自身的編程技巧稱為遞歸（ recursion）。

一般定義
程序調(diào)用自身的編程技巧稱為遞歸（ recursion）。
一個過程或函數(shù)在其定義或說明中有直接或間接調(diào)用自身的一種方法，它通常把一個大型復(fù)雜的問題層層轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復(fù)計算，大大地減少了程序的代碼量。遞歸的能力在于用有限的語句來定義對象的無限集合。一般來說，遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。
注意：
(1) 遞歸就是在過程或函數(shù)里調(diào)用自身；
(2) 在使用遞歸策略時，必須有一個明確的遞歸結(jié)束條件，稱為遞歸出口。

C#遞歸算法實例：

計算數(shù)組{1,1,2,3,5,8.......} 第30位值，不用遞歸，我寫出了以下這樣的代碼：

復(fù)制代碼代碼如下:

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#遞歸算法的使用，以下是代碼：

復(fù)制代碼代碼如下:

static void Main(string[] args)  
 ...{  

Console.WriteLine(Process1(30));  
Console.ReadLine();   
 }  
 public static int Process1(int i)  
 ...{  

//計算數(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);  
}  

復(fù)制代碼代碼如下:

// 階乘 
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);
        }
    }
}
// 斐波那契數(shù)列
public class Fibonacci { 
    public static void main(String[] args) {
        System.out.println(fibonacci(6));
    } 
    //  斐波那契數(shù)列：(從第三項開始,后一項都是前兩項的和)
    //  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());
                }
            }
        }
    }
}