Математическая техника для перевода рекурсии в цикл while()?

Question

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

Надеюсь, кто-нибудь может мне помочь.

Заранее спасибо.

Answer 1

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