数据结构学习（C++）之递归

数据结构学习（C++）之递归2008-01-05看过这样一道题，问，“程序结构化设计的三种基础结构，顺序、选择、循环是不是必须的？”当然，你知道这样一个论断，只要有这三种就足够了；但是能不能更少呢？答案是“可以”，原因就是递归能取代循环的作用，例如下面的对一个数组里面元素求和的函数：

float rsum （float a[], const int n）
{
if （n <= 0） return 0;
else return rsum（a, n – 1） + a[n – 1];
}

实际上就是：

sum = 0;

for （int i = 0; i < n; i++） sum += a[i];

但实际的情况是，任何的一种语言里面都有循环结构，但不是任何的语言都支持递归；套用一句话，递归是万能的，但没有递归不是万万不能的。然而，我看到现在的某些人，不管什么问题都要递归，明明循环是第一个想到的方法，偏偏费尽脑筋去寻找递归算法。对此，我真的不知道该说什么。

递归是算法吗

经常的看到“递归算法”、“非递归算法”，这种提法没有语义上的问题，并且我自己也这样用——递归的算法。但这也正说明了，递归不是算法，他是一种思想，正是因为某个算法的指导思想是递归的，所以才被称为递归算法；而一个有递归算法的问题，当你不使用递归作为指导思想，这样得到的算法就是非递归算法。——而对于循环能处理的问题，都有递归解法，在这个意义上说，循环算法都可以称为非递归算法。

我在这咬文嚼字没什么别的意思，只是想让大家知道，能写出什么样的算法，关键是看你编写算法时的指导思想。如果一开始就想到了循环、迭代的方法，你再费心耗神去找什么递归算法——即使找到了一种看似“简洁”的算法，由于他的低效实际上还是废物——你还在做这种无用功干什么？典型的学究陋习。如果你仅仅想到了递归的方法，现在你想用栈来消解掉递归，你做的工作仅仅是把系统做的事自己做了，你又能把效率提高多少？盲目的迷信消解递归就一定能提高效率是无根据的——你做的工作的方法如果不得当的话，甚至还不如系统原来的做法。