越夜越有机 发表于 2008-12-30 11:16:04

递归函数之JAVA演绎

1、递归函数的定义:
    答:递归函数即自调用函数,在函数体内直接或间接的调用自己,即函数的嵌套是函数本身。
    2、递归方式:递归调用有直接递归和间接递归两种方式。
    A:直接递归:在函数中出现调用函数本身。
    示例1:下面代码求斐波那契数列第n项,斐波那契数列第一和第二项是1,后面每一项是前两项之和,即1、1、2、3、5、8、13 。。。。
    程序代码:
    public class Test {
    public static void main(String args[]) {
    int x1 = 1;
    int sum = 0;
    int n = 7;
    for (int i = 1; i <= n; i) {
    x1 = func(i);
    sum = sum   x1;
    }
    System.out.println("sum="   sum);
    }
    public static int func(int x) {
    if (x > 2)
    return (func(x - 1)   func(x - 2));
    else
    return 1;
    }
    }
    B:间接递归:指函数中调用了其他函数,而该其他函数有调用了本函数。
    示例2:用间接递归来计算上述斐波那契数列。
    程序代码:
    public class Test {
    public static void main(String args[]) {
    int x1 = 1;
    int sum = 0;
    int n = 7;
    for (int i = 1; i <= n; i) {
    x1 = func1(i);
    sum = sum   x1;
    }
    System.out.println("sum="   sum);
    }
    public static int func1(int a){
    int b;
    b=func2(a);
    return b;
    }
    public static int func2(int b) {
    if (b> 2)
    return (func1(b - 1)   func1(b - 2));
    else
    return 1;
    }
    }
    3、为什么要用递归函数?递归函数的缺点是什么?
    答:递归的目的是简化程序设计,使程序易读。
    示例3:下面不用递归函数继续来计算上述斐波那契数列。
    程序代码:
    public class Test {
    public static void main(String args[]) {
    int n=7;
    int a=1, b=1, temp;
    int sum=2;
    for(int i=3; i<=n; i){
    temp=a b; a=b; b=temp;
    sum=sum temp;
    }
    System.out.println("sum="   sum);
    }
    }
    从上面例子我们可以发现虽然非递归函数效率高,但较难编程,可读性较差。递归函数的缺点是增加了系统开销,也就是说,每递归一次,栈内存就多占用一截。
    4、递归的条件:
    答:需有完成任务的语句,需满足递归的要求(减小而不是发散)。
5、递归进阶:
    示例4:
    编程求解:若一头小母牛,从出生起第四个年头开始每年生一头母牛,按次规律,第n年时有多少头母牛?
    程序代码:
    public class Test3 {
    public static void main(String args[]) {
    int n=10; //要查看的年数
    System.out.println("共有" cattle(n) "头小母牛!");
    }
    public static int cattle(int n){
    if(n<=0)
    return 0;
    if(n<=3)
    return 1;
    return cattle(n-1)cattle(n-3);//此处是递归要好好理解。
    }
    }
    规律:此类问题的递归函数为:
    如果要求的是从出生起第四个年头,则递归函数为cattle(n-1)cattle(n-3),
    如果要求的是从出生起第五个年头,则递归函数为cattle(n-1)cattle(n-4),
    ……
    依次类推。
页: [1]
查看完整版本: 递归函数之JAVA演绎