在解决约瑟夫问题时&＃xff0c;我比较推荐使用递归&＃xff0c;因为递归实现的算法代码更短&＃xff0c;逻辑也更清晰&＃xff0c;然而很多人有一个疑问&＃xff0c;那就是他们知道递归层数是有极限的&＃xff0c;这就意味着当需要很大层数的递归时&＃xff0c;递归算法是不可行的&＃xff0c;会导致段错误。
对于这个问题我有三个回答&＃xff1a;第一&＃xff0c;只要你使用的是计算机而不是你的大脑&＃xff0c;你就不要指望什么是无限制的&＃xff0c;计算机不是神&＃xff0c;计算机里别谈无限。第二&＃xff0c;虽然你的c代码是递归实现的&＃xff0c;但是编译器生成的二进制文件却不一定会递归调用一个函数&＃xff0c;这就涉及了编译器的优化。第三&＃xff0c;因为我们使用的大多数是x86体系的冯诺依曼机器&＃xff0c;这种机器的编译器一般对于函数调用是通过栈实现的&＃xff0c;而我们知道栈的预备空间和最大扩展空间一般都不会太大&＃xff0c;然而如果有一种机器&＃xff0c;根本就没有栈的概念&＃xff0c;或者说即使在x86机器上实现一个变态的编译器&＃xff0c;将函数调用退化成简单的jump而不使用栈操作&＃xff0c;那么栈的限制将不再存在。
在基于栈实现函数调用的机器上&＃xff0c;我们看一下在什么情况下必须层层嵌套用递归实现。其中一个条件&＃xff0c;那就是在递归的过程中&＃xff0c;我们无法获知任何计算的中间结果&＃xff0c;必须等到最深入一层的函数满足非递归条件而返回时&＃xff0c;整个过程才会一层一层的返回&＃xff0c;但是如果每一步的中间结果都被保存或者说每一步的递归过程并不是要计算什么值&＃xff0c;而仅仅是为了实现一个副作用&＃xff0c;那么最终的二进制文件大可不必非要用递归。而且我们知道&＃xff0c;递归和迭代是等价的&＃xff0c;这一点非常重要。
编译器不是傻子-其实是实现编译器的人很聪明&＃xff0c;编译器一定不会傻到非要用递归生成最终的二进制执行文件&＃xff0c;以gcc为例&＃xff0c;即使你在c函数中明确使用了递归&＃xff0c;在-O3的优化编译选项下&＃xff0c;编译器还是会尝试将递归化为迭代的&＃xff0c;所生成的二进制objdump文件中你将看不出任何递归调用&＃xff0c;这种工作并不是你自己实现的&＃xff0c;而是编译器帮你实现的。
有一种递归被叫做“尾递归”&＃xff0c;对于这种递归的理解其实很简单&＃xff0c;那就是每一步递归调用的中间结果被保存&＃xff0c;因此你可以只使用一个栈帧实现所有的递归过程&＃xff0c;因为中间结果随着递归的深入而持续改变&＃xff0c;因此你可以将其理解为一种隐含的迭代。对于约瑟夫问题&＃xff0c;这种尾递归是很显然的&＃xff0c;因为每一步的递归过程的效果其实都是一种副作用&＃xff0c;那就是在链表上删除一个节点。但是你还是要告诉编译器这一切&＃xff0c;否则编译器仍然使用递归过程生成二进制代码。
最终的结果&＃xff0c;你用-O3选项编译这个c文件&＃xff0c;使用objdump查看其目标码&＃xff0c;你将看不到任何递归过程&＃xff0c;这就突破了栈的限制&＃xff0c;但是记住&＃xff0c;限制仍然是有的&＃xff0c;因为很抱歉&＃xff0c;你用的是计算机这种奴隶式的工具&＃xff0c;计算机说的最多的话&＃xff0c;那就是&＃xff1a;Sorry, it is beyond my ablity!
京公网安备 11010802041100号