为什么递归的二进制搜索有时会导致一些而不是所有不存在的输入的堆栈溢出？
递归的二进制搜索有时会导致一些而不是所有不存在的输入的堆栈溢出，原因如下：
递归的二进制搜索算法是一种通过将搜索空间逐渐缩小一半来寻找目标元素的方法。它将搜索范围一分为二，然后根据目标值与中间值的大小关系，确定继续搜索的方向。如果目标值小于中间值，则继续在左半部分搜索；如果目标值大于中间值，则继续在右半部分搜索；如果目标值等于中间值，则找到目标元素。
当搜索的目标元素不存在时，递归的二进制搜索会在每次划分搜索空间之后继续对剩余部分进行递归调用。每次递归调用都会将搜索空间缩小一半，直到搜索空间为空或找到目标元素为止。
然而，当目标元素不存在时，递归的二进制搜索会不断划分搜索空间，最终将搜索空间缩小到只剩下一个元素。此时，如果继续进行递归调用，就会导致堆栈溢出。
堆栈溢出的原因是每次递归调用会在堆栈中创建一个新的函数调用帧，用于保存函数的局部变量、返回地址等信息。由于递归的二进制搜索会不断进行递归调用，导致堆栈中的函数调用帧数量过多，超出了堆栈的容量限制，从而导致堆栈溢出。
为了避免递归的二进制搜索导致堆栈溢出，可以采取以下几种方法：
- 使用非递归的二进制搜索算法，利用循环来替代递归调用，可以避免堆栈溢出的问题。
- 在递归调用之前，添加对搜索空间是否为空的判断，当搜索空间为空时，立即结束递归调用，避免不必要的递归操作。
- 当目标元素不存在时，可以通过返回特定的值或抛出异常来表示搜索失败，而不是继续进行递归调用。
腾讯云相关产品：
- 腾讯云函数（云原生）：https://cloud.tencent.com/product/scf
- 腾讯云搜索（文本搜索服务）：https://cloud.tencent.com/product/css
- 腾讯云堆栈（弹性Web托管）：https://cloud.tencent.com/product/tiw
相关·内容
我正在实现一个递归的python二进制搜索函数，它对大多数输入都很有效，但似乎会导致一些不存在的列表元素的堆栈溢出，我不明白为什么代码会出现这种行为 def recursive_binary_searchres = recursive_binary_search(middle_index+1, end, search, array)
return
浏览 25提问于2020-11-07得票数 0
回答已采纳
我想知道java.lang.StackOverflowError的根本原因是什么。我知道当方法被递归调用无限次时就会发生这种情况，但是异常的实际原因是什么，默认的堆栈大小是多少？
浏览 0提问于2014-02-27得票数 2
1回答
return foo(x,y-1); }
我们现在要展示的是，是否有可能构造一个数学集T，当它作为一个Java类实现并用作该函数的输入时，它总是会导致函数终止因此，集合T必然只包含非负整数.但是对于int的大型元素，该函数也会导致堆栈溢出。这是有意义的，因为int的最大值是2,147,483,647。因此，foo(2147483647, 2147483647)将<em
浏览 2提问于2019-12-18得票数 0
回答已采纳
4回答
注意:这个问题涉及堆栈溢出(考虑无限递归)，而不是缓冲区溢出。
如果我写的程序是正确的，但它接受来自Internet的输入，该输入决定了它调用的递归函数中的递归级别，这是否足以让某人危害机器？我知道有人可能会通过导致堆栈溢出来使进程崩溃，但是他们会注入代码吗？或者c运行库是否
浏览 2提问于2010-11-05得票数 8
回答已采纳
1回答
我正在尝试使用Python3.6中的递归来寻找一个大数的阶乘。尽管我已经将递归限制设置为10**9，但是仍然运行代码会导致内核死机。我知道迭代解决方案要好得多，但我想知道为什么会这样mod = 10**9+7def fac(n):
if(n
浏览 0提问于2020-08-10得票数 0
我目前在Coursera上关注Tim Roughgarden的算法专门化，模块2，第一周的作业涉及计算图中强连接分量的大小。我可以为较小的图形计算它们，但是这个问题有大约500万条边。我有一个解决方案工作得相当快，但我花了几个小时试图让它在全套设备上运行，除了我在AWS超级计算机上购买了一些时间之外，有人能帮我找到解决堆栈溢出错误的方法吗？我已经跳过了预处理步骤，我将数组放入邻接列表中，并以正确的顺序将其传递到master_dfs中。
浏览 0提问于2018-12-20得票数 0
我的问题是，当我使用递归时，我通常会得到一个java.lang.StackOverflowError。我的问题是-为什么递归导致堆栈溢出比循环多得多，有没有使用递归来避免堆栈溢出的好方法？这是解决的一种尝试，它对他们的示例工作得很好，但对于问题本身来说，堆栈空间已经用完了。
浏览 0提问于2013-08-22得票数 12
在C++链表中使用递归和迭代来分隔偶数和奇数长度的字符串，哪个更好？
更好的方法1)健壮性2)跨平台Windows/Linux/Unix可移植性3)最坏情况下的运行时性能。
浏览 1提问于2012-12-31得票数 1
回答已采纳
1回答
我正在将我的用户应用程序转换为内核模块。内核模块使用200M内存(所有内存都是通过vmalloc()获得的)。此内存用于递归哈希表。我使用了一个递归函数来删除哈希表。递归调用的数量可以达到数千次(因为使用的总内存是200M，而每个哈希表的大小只有256*8 )。
问题是，当我使用递归函数删除哈希表时，内核有时会崩溃。相同的应用程序在用户空间中运行时，不会崩溃，并且
浏览 5提问于2016-05-24得票数 0
1回答
谁能解释一下为什么在递归调用期间堆栈溢出会导致总线错误而不是分段错误(Mac )？
我有一个被递归调用了几千次的函数。正如我预期的那样，它达到了堆栈限制，但在其他情况下，这会导致分段错误，这是合乎逻辑的，但为什么它是总线错误10？据我所知，引用未对齐的内存会导致总线错误，但为什么在达到
浏览 20提问于2019-07-31得票数 2
2回答
下一段来自
同时，递归不会导致Racket中的性能特别差，并且没有堆栈溢出这样的事情；如果计算涉及太多的上下文，您可能会耗尽内存，但是耗尽内存通常需要更深的递归，而不是触发其他语言中的堆栈溢出。我很好奇球拍是如何设计来避免堆叠溢出的？更重要的是，为什么像C这样的</
浏览 1提问于2018-04-19得票数 3
4回答
我试图找到一种不用递归删除链接列表的方法，因为堆栈溢出并不是什么好事。我的结构如下：{ {}
在一些代码(这里不相关)中，我正在使用上面的结构从一个数据文件构建一个列表。我将指向列表头的指针保存在一个变量中，并且可以使用
浏览 6提问于2014-02-05得票数 3
回答已采纳
来自：
返回递归限制的当前值，即Python解释器堆栈的最大深度。这个限制防止无限递归导致C堆栈溢出和Python崩溃。它可以通过set递归限制()来设置。
当前，当选择对象时，我会遇到递归限制。我正在挑选的对象只有几个层次的嵌套，所以我对正在发生的事情感到有点困惑。try上获得成功，有时会在第二个try上获
浏览 7提问于2015-12-06得票数 20
回答已采纳
1回答
当我使用VS 2015进入调试模式的函数时，我会得到一个堆栈溢出错误。在这两种情况下(当函数运行时，以及当它导致堆栈溢出时)，将使用相同的输入参数(大约300个base64编码的xml)调用它。因此，当我用所有未注释的代码编译时，我会导致函数的执行/内存分配出现问题，但我不明白是什么原因。编辑
在搜索__chkstk()之后，我刚刚找到
浏览 2提问于2018-08-16得票数 1
回答已采纳
5回答
自从我在大学学习数据结构和算法以来已经有很长一段时间了，所以最近我惊讶地发现，递归可能不是 (tm)进行树遍历的方式。出于某种原因，基于队列的遍历并不是我曾经使用过的技术。如果有的话，迭代遍历和递归遍历的优点是什么？在什么情况下我可以使用其中一种而不是另一种？
浏览 15提问于2009-04-16得票数 14
回答已采纳
一些在作业中出现的事情，可能是因为我的土豆笔记本电脑，但我感兴趣的是，当StackOverflow发生在一个不平衡的BST (故意)。因此，我比较了搜索AVL树和不平衡BST的最差性能，搜索元素的方法也适用于AVL，但是我得到了StackOverflow错误。BST最终只是一个链接列表，其中输入了“坏数据”(按字母顺序排列的名称；大约为10000)，那么对entryExists的调
浏览 3提问于2017-04-22得票数 0
回答已采纳
2回答
在不同的地方，我看到了使用堆栈实现快速排序比使用递归更快的说法。这是真的吗？我知道编译器通常擅长将递归转换为迭代，但是链接到页面上的注释要求它过于复杂，无法进行优化。
尽管如此，函数仍然是递归的，使用函数调用堆栈存储中间值l和h，函数调用堆栈存储其他簿记信息和参数。然而，答案指出，这并
浏览 2提问于2014-07-15得票数 1
我对Java的线程世界比较陌生，需要一些帮助。我正在使用一种深度递归算法来构建一个基于Graphstream ()库的图。但是，我遇到了Stackoverflow错误。我确信我的算法是正确的(我在小规模上进行了测试)。
我读到了关于线程的文章，以及线程是如何帮助你的。我的想法是为每个递归生成一个新的线程(可能会达到数百万:( )..这也会生成很多子图。最后，我将不得不将所有这些子图
浏览 2提问于2013-07-22得票数 1
回答已采纳
4回答
如何调试无跟踪崩溃
、、、、
我们有处理SEH和正常异常的特殊功能，所以所有这些都不应该被忽略。OpenGLDirectshow +一些COTS filtersCOM/DCOMSerial COM端口与专用硬件C++ Builder (使用与VC++不同
浏览 4提问于2011-03-01得票数 4
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
实时音视频活动推荐
腾讯云开发者
