递归、递归算法的非递归优化

一：递归
在方法内部调用自身方法的过程称为递归，下面给出一个递归方法的示例。

class Program
{
    static void Main(string[] args)
    {
        int sum = GetSum(5);                //递归方法，获得1~5的累加和
        Console.WriteLine("sum = " + sum);
        Console.ReadKey();
    }
    //使用递归，实现求前n项和
    public static int GetSum(int n)
    {
        if (n == 1)
        {
            return 1;                       //满足条件，递归结束
        }
        int result = GetSum(n - 1);         //在方法体中调用方法本身
        return result + n;
    }
}

需要注意的是，递归方法需要有结束递归的条件，如果不加条件，就会陷入无限递归的状态；

二：递归算法的非递归优化
在上面示例中，我们用递归实现的求数列前n项和，那么我们下面试试，不用递归来实现求数列前n项和。

class Program
{
    static void Main(string[] args)
    {
        int sum = GetSum2(5);                //调用非递归方法，获得1~5的累加和
        Console.WriteLine("sum = " + sum);
        Console.ReadKey();
    }
    // 非递归，实现求前n项和
    public static int GetSum2(int n)
    {
        int result = 0;
        for (int i = 0; i < n; i++)
        {
            result = result + i;
        }
        return result + n;
    }
    //使用递归，实现求前n项和
    public static int GetSum(int n)
    {
        if (n == 1)
        {
            return 1;
        }
        int result = GetSum(n - 1);
        return result + n;
    }
}

在上面的示例中，我们可以看到，不适用递归算法时，我们使用的是循环结构；所以对于部分递归算法的非递归优化，使用循环结构是一种解决办法！