Какова максимальная глубина рекурсии?

Question

Мне интересно, какая максимальная глубина функции рекурсии. Я знаю, что он имеет отношение к размеру стека. Но каковы отношения? Если я напишу функцию в 32-битной машине, которая ничего не дозирует, но называет себя, какая максимальная глубина?

unsigned long times=0; 
void fun() 
{ 
    ++times; 
    fun(); 
} 

Тогда что такое значение «раз» при переполнении стека?

Answer 1

Отношения примерно следующим образом:

Максимальная глубина рекурсии = ((размер стека) - (Общий размер кадров стека в цепочке вызовов до рекурсивной функции))/(Стек размер кадра рекурсивным функция)

Фрейм стека - это данные, которые попадают в стек при каждом вызове функции. Он состоит из адреса возврата функции, пространства для параметров (которые не были переданы в регистры) и пространства для локальных переменных. Он будет отличаться для разных функций, но он будет постоянным для данной функции, рекурсивно вызывающей себя при каждом вызове.

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

Если компилятор выполняет оптимизацию хвостовой рекурсии, тогда размер кадра стека фактически равен нулю после вызова верхнего уровня, поэтому формула дает деление на ноль: нет максимальной глубины рекурсии.

Все, что я сказал здесь, вероятно, имеет несколько исключений из правила, но это основные отношения.