学步园

      今天，在论坛上，看到一个求助解释递归代码的问题。这不由使我想起自己半年前，学习递归算法的痛苦。在此，我以一个简单的例子，通过数学归纳法，来解释递归的基本原理。希望能给正在学习递归的人，得以启发，有以帮助。

      求：1+2+3+...100的和（这没必要用递归，只是举个简单例子，希望能解释清楚递归）
      递归就是类似于数学归纳法。
      令sum(n)表示1+2+3+...+n(n>0)
      则sum(1) = 1,sum(n)=sum(n-1)+n

      代码如下：

public class RecursionExample {
    public static void main(String args[]){
        System.out.println(addAll(100));
    }
    /**
     * 默认addEnd>0,求1+2+3+...+100
     * @param max 最大相加项
     * @return  所求之和
     */
    public static int addAll(int max){
        //令sum(n)表示1+2+3+...+n(n>0)

        //sum(1)=1
        if(max==1){
            return(1);
        }

        //sum(n)=sum(n-1)+n
        else{
            return(max + addAll(max-1));
        }
    }
}

      通常，1+2+3+...+100都是用for、while语句，从1开始，逐项相加，直到100。

      在这段程序中，从100开始加起，欲知sum(100)，只要把sum(99)加上100即可；欲知sum(99)，只要把sum(98)加上99即可。。。。。。直到sum(1)，满足结束递归的条件，返回1。

      之后，sum(2)就可以由2+sum(1)求得并返回，sum(3)可以由3+sum(2)求得并返回。。。。。。

      最后，求得sum(100)。