Как правило, нет алгоритма для преобразования рекурсивной формы в итеративную. Эта проблема неразрешима. В качестве примера рассмотрим определение рекурсивной функции, которое определяет последовательность Коллатца:
f(1) = 0
f(2n) = 1 + f(n)
f(2n + 1) = 1 + f(6n + 4)
Неизвестно, является ли эта функция четкой или нет. Если бы существовал алгоритм, который мог бы преобразовать это в замкнутую форму, мы могли бы решить, был ли он четко определен.
Однако во многих распространенных случаях можно преобразовать рекурсивное определение в итеративное. Отличный учебник «Бетонная математика» проводит большую часть своих страниц, показывая, как это сделать. Одна из распространенных техник, которая работает достаточно хорошо, когда вы догадываетесь, каков ответ, - это использование индукции. В качестве примера для вашего случая предположим, что вы считаете, что ваше рекурсивное определение действительно дает 3 ^ n - 1. Чтобы доказать это, попробуйте доказать, что оно верно для базовых случаев, а затем показать, что эти знания позволяют обобщить решение в сторону увеличения , Вы не поместили базовый случай в свой пост, но я предполагаю, что
f(0) = 0
f(1) = 2
Учитывая это, давайте посмотрим, верна ли ваша догадка. Для конкретных входов 0 и 1 вы можете проверить путем проверки, что функция действительно вычисляет 3 ^ n - 1. Для индуктивного шага предположим, что для всех n '
f(n) = 2f(n - 1) + 3f(n - 2) + 4
= 2 * (3^{n-1} - 1) + 3 * (3^{n-2} - 1) + 4
= 2 * 3^{n-1} - 2 + 3^{n-1} - 3 + 4
= 3 * 3^{n-1} - 5 + 4
= 3^n - 1
Итак, мы только что доказали, что эта рекурсивная функция действительно производит 3 ^ n - 1.