首页 > 代码库 > 递归案例

递归案例

一般定义
程序调用自身的编程技巧称为递归( recursion)。
一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。
注意:
(1) 递归就是在过程或函数里调用自身;
(2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。

C#递归算法实例:

计算数组{1,1,2,3,5,8.......} 第30位值,不用递归,我写出了以下这样的代码:

  1. static void Main(string[] args)  
  2.  ...{  
  3.  
  4. int[] num=new int[30];  
  5. num[0]=1;  
  6. num[1]=1;  
  7. int first=num[0];  
  8. int second=num[1];  
  9. for (int i = 2; i < num.Length; i++)  
  10. ...{  
  11.  num[i] = first + second;  
  12.  first = second;  
  13.  second = num[i];  
  14. }  
  15. Console.WriteLine(num[29]);  
  16. Console.ReadLine();  
  17.  
  18.  }  

C#递归算法的使用,以下是代码:

  1.  static void Main(string[] args)  
  2.  ...{  
  3.  
  4. Console.WriteLine(Process1(30));  
  5. Console.ReadLine();   
  6.  }  
  7.  public static int Process1(int i)  
  8.  ...{  
  9.  
  10. //计算数组{1,1,2,3,5,8.......} 第30位值  
  11. if (i == 0) return 0;  
  12. if (i == 1) return 1;  
  13. else 
  14. return Process1(i - 1) + Process1(i - 2);  
  15. }  

// 阶乘 

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());

                }

            }

        }

    }

}