Answers
- 如何去设计一个递归？ 这是一个很大的主题，推荐你看看 SICP （计算机程序的构造和解释）或者 How to Design Programs ，SICP里面用了很大的篇幅讲了如何用递归去思考程序，并且比较了用递归去写程序和用迭代方式去写程序的区别（由于要记住每次迭代的状态，强迫程序员考虑每一步赋值的先后顺序，因而增加的程序员的思维负担），且其作者进一步的认为，递归更符合人的直觉，且以纯函数的方式来进行计算机程序设计的入门教学是一种更好的选择。
- 怎么用一般的方法去求得结果? 我的理解是，你要用迭代的方式来替代递归。通常情况下一个算法用递归的方式来表现更容易让程序员理解（有不同意见？）个人理解递归反而是更一般的方法，因此很多算法书上的算法都是用递归的方式来写伪代码的。在一些高级的程序设计语言里，如lua或者scheme，当使用递归的方式是尾递归(tail call or tail recursion)时，编译器自动为其进行优化，效率和速度和利用一般的迭代相同, 在其它没有优化尾递归的语言中如c，要用迭代来替换递归也是很简单和直观的。较复杂的递归程序设计要转换成迭代的方式，有时候较麻烦。上面你这个程序采用递归的方式实现，其实质是编译器通过调用堆栈的方式替你保存了程序的中间变量，当程序员用迭代来替代递归时，这些保存中间变量的麻烦事就交给程序员来做了，通过显式维护一个stack可较为方便得将递归转换为迭代的方式。关于递归和迭代的相互转换可参见： 递归转为迭代 ； 迭代转为递归
到处逛着玩儿
answered 12 years, 7 months ago