我是新来的，有一个问题困扰着我。我是初学者，所以请不要嘲笑我。我想对大量元素进行递归快速排序，比如说 100000。我知道这会导致堆栈溢出。过去几天我一直在谷歌搜索，试图找到一种管理调用堆栈的方法。我可以真的找不到好的信息来源。我的想法是删除每个递归调用的返回地址，除了最后一个，它将返回到第一个函数调用。我不知道这是否可能，或者它是否是这个问题的另一种解决方案。
PS：我想保持快速排序递归。
对不起，如果我的问题看起来很傻，但我很高兴任何相关的答案。对不起，我的英语不好。谢谢！
问问题
277 次
4 回答
3
使用递归算法解决堆栈空间不足问题的标准方法是迭代地实现它。
于 2012-04-03T23:34:22.847 回答
3
请注意，数组中的 100000 个项目什么都不是；这只会导致嵌套调用 17 个函数深：
$ echo "l(100000)/l(2)" | bc -l
16.60964047443681173951
那就是log(N)/log(2)-log(2)将其转换为对数基数 2。
任何支持递归函数调用的平台几乎肯定能够处理 17 个嵌套调用。
于 2012-04-03T23:44:48.410 回答
1
如果堆栈空间是一个问题，但内存通常不是问题，您可以通过使用自己的堆分配堆栈轻松地将递归实现转换为迭代实现。也就是说，不是进行递归函数调用，而是将您关心的参数推送到您自己的堆栈数据结构中。然后，您可以遍历您的堆栈并处理每组参数。
于 2012-04-03T23:41:03.703 回答
0
听起来您正在尝试进行尾递归，已在此处讨论过；
于 2012-04-04T08:41:35.210 回答