Можно ли переписать каждую рекурсивную функцию как итеративную функцию?

Question

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

Например,

factorial(n) { 
    if (n==1) { return 1 } 
    else  { return factorial(n-1) } 
} 

Это можно легко переписать итеративно:

factorial(n) { 
    result = 1; 
    for (i=1; i<=n; i++) { 
     result *= i 
    } 
    return result 
} 

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

Answer 1

Да, рекурсивная функция всегда может быть записана как итерация с теоретической точки зрения - это обсуждалось before. Цитата из связанного сообщения:

Поскольку вы можете построить полный язык Тьюринга, используя строго итерационные структуры и язык Turning complete, используя только рекурсивные структуры, тогда эти два эквивалентны.

Пояснение немного: мы знаем, что любая вычислимая проблема может быть решена машиной Тьюринга. И можно построить язык программирования A без рекурсии, что эквивалентно машине Тьюринга. Аналогичным образом, можно построить язык программирования B без итерации, равный вычислительной мощности машине Тьюринга.

Следовательно, если оба A и B равны Turing-complete, мы можем заключить, что для любой итеративной программы должна существовать эквивалентная рекурсивная программа, и наоборот. Это теоретический результат в том смысле, что он не дает вам никаких намеков на то, как вывести одну рекурсивную программу из произвольной итеративной программы или наоборот.

Answer 2

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