如何将递归算法转化为非递归优化实现？

本文共计464个文字，预计阅读时间需要2分钟。

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

csharpclass Program{ static void Main(string[] args) { int sum=GetSum(5); // 递归方法，获取1到5的累加和 Console.WriteLine(1到5的累加和为： + sum); }

static int GetSum(int n) { if (n <=1) return n; return n + GetSum(n - 1); }}

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

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; } }

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