递归学习笔记 - AriesH的博客

作者在 2008-10-18 16:44:36 发布以下内容

什么使递归?
递归是一个直接或间接调用自身的方法.
基本递归规则.
①基本情况:至少有一种情况可以不用递归解决.
如n=1是就不需要递归解决
②前进:任何递归调用必须朝着基本情况前进.
③总是假设递归调用是可行的.
④复利规则:永远不要在不同的递归调用中重复执行解决同一问题实例的工作.

记住:不要用递归代替简单的循环

/**
 * 基本的递归算法
 *以任何数值打印数
 * @author HuangYunLin
 */
public class Recursive {

    public void printDecimal(long n) {
        if (n >= 10) {
            printDecimal(n / 10);
            System.out.print(n+"\n");//如一个栈,递归是一个自然的副产品,方法调用和方法返回使栈操作
            //自己做个调试你就会明白这点道理了!
        }
        System.out.print((char) ('0' + (n % 10)) + "\n");
    }

    public void printInt(long n, int base) {
        String DIGIT_TABLES = new String();
        if (n >= 10) {
            printInt(n / base, base);
        }
        System.out.print(DIGIT_TABLES.charAt((int) (n % base)));
    }
    /*------------------------------------------------------------------*/
    /**
     * 改进上面的算法,在改进算法中我们加入判断程序.
     * 测试base的合法行
     */
    private static final String DIGIT_TABLE = "0123456789abcdef";//16位
    private static final int MAX_BASE = DIGIT_TABLE.length();

    public void printIntRec(long n, int base) {
        if (n >= 10) {
            printIntRec(n / base, base);
        }
        System.out.print(DIGIT_TABLE.charAt((int) (n % base)));
    }

    public void printInts(long n, int base) {
        //输入的base<16;
        if (base <= 1 || base > MAX_BASE) {
            System.err.println("cannot print int base" + base);
        } else {
            if (n < 0) {
                n = -n;
                System.err.println("-");
            }
            printIntRec(n, base);
        }
    }
    /**
     * 总结:递归程序总是可以用栈迭代地实现.
     * 递归总是可以用栈代替,为了节约空间,有时需要这样做.
     */
}