当前位置:编程学习 > JAVA >>

递归 递归算法

概述
程序调用自身的编程技巧称为递归( recursion)。递归做为一种算法在程序设计语言中广泛应用。递归有直接递归和间接递归
•直接递归:函数在执行过程中调用本身。
•间接递归:函数在执行过程中调用其它函数再经过这些函数调用本身。
•表达方式:
•递归算法有四个特性:
(1)必须有可最终达到的终止条件,否则程序将陷入无穷循环;
(2)子问题在规模上比原问题小,或更接近终止条件;
(3)子问题可通过再次递归调用求解或因满足终止条件而直接求解;
(4)子问题的解应能组合为整个问题的解。
 
下面将从以下几个典型的例子来讲解递归算法:
 
汉诺塔问题
如图,汉诺塔问题是指有三根杆子A,B,C。C杆上有若干碟子,把所有碟子从C杆上移到B杆上,每次只能移动一个碟子,大的碟子不能叠在小的碟子上面。求最少要移动多少次?
当n=1时:
Move  1  from  A  to  C
当n=1时:
Move  1  from  A  to  B
Move  2  from  A  to  C
Move  1  from  B  to  C
当n=1时:
Move  1  from  A  to  C
Move  2  from  A  to  B
Move  1  from  C  to  B
Move  3  from  A  to  C
Move  1  from  B  to  A
Move  2  from  B  to  C
Move  1  from  A  to  C
源代码
[java]  
static StringBuffer str = new StringBuffer();  
    /** 
     * //汉诺塔问题 
     * @param n 盘子的个数 
     * @param x 将要移动盘子柱子 
     * @param y 要借用的柱子 
     * @param z 要移动到的柱子 
     * @return 
     */  
    public static String hanio(int n, Object x, Object y, Object z) {  
        //String str ="";  
        if(1 == n)   
            str.append(move(x, n, z) + "\n");  
        else {  
            hanio(n-1, x, z, y);  
            str.append(move(x, n, z) + "\n") ;  
            hanio(n-1, y, x, z);  
        }  
        return str.toString();  
    }  
    private static String move(Object x, int n, Object y) {  
        //System.out.println("Move  " + n + "  from  " + x + "  to  " + y);  
        return "Move  " + n + "  from  " + x + "  to  " + y;  
    }  
      
 
fibonacci数列
斐波纳契数列,又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21、……在数学上,斐波纳契数列以如下被以递归的方法定义:F0=0,F1=1,Fn=F(n-1)+F(n-2)(n>=2,n∈N*)
源代码
[java] 
/** 
     * fibonacci数列 
     * @param n 
     * @return 
     */  
    public static long fibonacci(int n) {  
        if((0 == n) || (1 == n)) {  
            return n;  
        }else {  
            return fibonacci(n-1) + fibonacci(n-2);  
        }  
    }  
 
 
1加到n累加
用递归实现从1加到n,即1+2+3+4+...+n。
源代码
[java]  
/** 
     * 累加,从1加到n,即1+2+3+4+...+n 
     * @param n 要累加到的数值 
     * @return 累加的结果 
     */  
    public static long total(int n) {  
        if(1 == n) {  
            return n;  
        }else {  
            return total(n-1) + n;  
        }  
    }  
 
 
从1到n累积
用递归实现,从1到n累积,即1*2*3*...*n
源代码
[java] 
/** 
     * 从1到n的累积,即1*2*3*...*n 
     * @param n 要累乖到的数值 
     * @return 
     */  
    public static long accumulate(int n) {   
        if(1 == n) {  
            return n;  
        }else {  
            return accumulate(n-1) * n;  
        }  
    }  
 
 
求数组中的最大值
用递归算法求数组中的最大值。
源代码
[java]  
/** 
     * 用递归算法求数组中的最大值 
     * @param a 数组 
     * @param low 数组下标 
     * @param heigh 数组上标 
     * @return 
     */  
    public static int Max(int[] a, int low, int heigh) {  
        int max;  
        if(low > heigh-2) {  
            if(a[low] > a[heigh]) max = a[low];  
            else max = a[heigh];  
        }else {  
            int mid = (low + heigh)/2;  
            int max1 = Max(a, low, mid);  
            int max2 = Max(a, mid+1, heigh);  
            max = max1>max2 ? max1 : max2;  
        }  
        return max;  
    }  
 
 
数字塔问题
用递归算法求解数字塔问题。
n=1时
1
n=2时
1      
2      2      
n=3时
1      
2      2      
3      3      3   
n=4时
1
补充:软件开发 , Java ,
CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络,