Как узнать предельную глубину рекурсии?
Так как вызовы функций при выполнении программы происходят через стек - область памяти, размер которой ограничен и известен в момент запуска потока приложения, то может возникнуть ситуация, когда стек переполнится от слишком большого количества рекурсивных вызовов.
Самый простой способ проверить, насколько глубокой может быть рекурсия в вашем компиляторе - запустить из-под него программку, которая неограниченное количество раз рекурсивно вызывает саму себя. На каком числе "рухнет", такова и "предельная глубина" рекурсии. У меня вышло 3992 в консоли Visual Studio 2019 на платформе x64.
Не следует думать, что количество вызовов, на котором программа прекратит работать, "безопасно". Ведь через стек передаются также аргументы функции (а у нас он всего один и целочисленный) и там же создаются локальные переменные функции (а у нас их нет вообще).
#include <iostream> void recurse(unsigned int i) { std::cout << i << "\n"; recurse(i + 1); } int main() { recurse(0); }
PHP 7.4 из-под XAMPP показал значение 3259619:
<?php function a() { static $i = 0; print ++$i . "\n"; a(); } a(); ?>
Конечно, при проверке можно задействовать и механизм обработки исключений, если он есть в языке, в том числе и интерпретируемом.
Вот что вышло у меня для JavaScript:
<script> function recurse(depth) { try { return recurse(depth + 1); } catch(ex) { return depth; } } var maxRecursion = recurse(1); document.write("Recursion depth is " + maxRecursion); </script>
Recursion depth on this system is 24628
09.05.2020, 13:57 [1781 просмотр]