Java数据结构和算法(九)——递归

递归的定义

递归,就是在运行的过程中调用自己。
递归必须要有三个要素:
①、边界条件
②、递归前进段
③、递归返回段
当边界条件不满足时,递归前进;当边界条件满足时,递归返回。

求一个数的阶乘:n!

规定:
①、0!=1
②、1!=1
③、负数没有阶乘
上面的表达式我们先用for循环改写:

/**
* 0!=1  1!=1
* 负数没有阶乘,如果输入负数返回-1
* @param n
* @return
*/
public static int getFactorialFor(int n){
    int temp = 1;
    if(n >=0){
        for(int i = 1 ; i <= n ; i++){
            temp = temp*i;
        }
    }else{
        return -1;
    }
    return temp;
}

递归实现

/**
* 0!=1  1!=1
* 负数没有阶乘,如果输入负数返回-1
* @param n
* @return
*/
public static int getFactorial(int n){
    if(n >= 0){
        if(n==0){
            System.out.println(n+"!=1");
            return 1;
        }else{
            System.out.println(n);
            int temp = n*getFactorial(n-1);
            System.out.println(n+"!="+temp);
            return temp;
        }
    }
    return -1;
}
递归存在的问题

大数递归出现栈溢出,建议采用循环方式实现

评论

暂无评论