БлогNot. Как узнать предельную глубину рекурсии?

Как узнать предельную глубину рекурсии?

Так как вызовы функций при выполнении программы происходят через стек - область памяти, размер которой ограничен и известен в момент запуска потока приложения, то может возникнуть ситуация, когда стек переполнится от слишком большого количества рекурсивных вызовов.

Самый простой способ проверить, насколько глубокой может быть рекурсия в вашем компиляторе - запустить из-под него программку, которая неограниченное количество раз рекурсивно вызывает саму себя. На каком числе "рухнет", такова и "предельная глубина" рекурсии. У меня вышло 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 [1780 просмотров]


теги: c++ программирование javascript php тест

К этой статье пока нет комментариев, Ваш будет первым