Рекурсия и итерация

Question

В чем разница? Это то же самое? Если нет, может кто-нибудь, пожалуйста, приведи пример?

MW: Итерация - 1: действие или процесс итерации или повторения: как: процедура, при которой повторение последовательности операций дает результаты последовательно ближе к желаемому результату b: повторение последовательности компьютерное задание определенное количество раз или до тех пор, пока не будет выполнено условие

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

Answer 1

Мы можем различать (как это сделано в SICP) рекурсивные и итерационные процедуры от recursive and iterative processes. Первые, как описано в вашем определении, где рекурсия в основном такая же, как математическая recursion: a recursive procedure определяется в терминах самого себя.Итеративная процедура повторяет блок кода с помощью оператора цикла. Рекурсивный процесс, однако, является тем, который принимает непостоянный (например, O(n) or O(lg(n)) space) для выполнения, в то время как итеративный процесс занимает O (1) (постоянное) пространство.

Для математических примеров, числа Фибоначчи определяются рекурсивно:

Sigma notation аналогичен итерации:

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

Answer 2

Вот функция Lisp для нахождения длины списка. Это рекурсивное:.

(defun recursive-list-length (L) 
    "A recursive implementation of list-length." 
    (if (null L) 
     0 
    (1+ (recursive-list-length (rest L))))) 

Он гласит: «длина списка либо 0, если этот список пуст, или 1 плюс длина подсписка начиная со вторым элементом)

И это реализация strlen - функция C найти длину NUL завершающих char* строки это итеративное:.

size_t strlen(const char *s) 
{ 
    size_t n; 

    n = 0; 
    while (*s++) 
     n++; 
    return(n); 
} 

вы цель состоит в том, чтобы повторить какую-то операцию с помощью итерации, вы используете явный цикл (например. while loo p в коде strlen). Используя рекурсию, ваша функция вызывает себя (обычно) меньшим аргументом и так далее до тех пор, пока не будет выполнено граничное условие (null L в коде выше). Это также повторяет операцию, но без явного цикла.

Answer 3

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

Например. Итерационный алгоритм факторного расчета

fact=1 
For count=1 to n 
fact=fact*count 
end for 

И рекурсивная версия

function factorial(n) 
if (n==1) return 1 
else 
n=n*factorial(n-1) 
end if 
end function 

Вообще

Рекурсивный код более лаконичный, но использует больший объем памяти. Иногда рекурсии можно преобразовать в итераций с использованием dynamic programming.

Answer 4

[Спешите и козырь этого!]

Одной из форм может быть преобразована в другую, с одним известным ограничением: многие «популярные» языки (C/Java/нормальный Python) не поддерживают TCO/TCE (оптимизация хвостового вызова/исключение хвоста), и, таким образом, использование рекурсии будет «добавлять дополнительные данные в стек» каждый раз, когда метод вызывает себя рекурсивно.

Итак, в C и Java итерация идиоматична, тогда как в схеме или Haskell рекурсия является идиоматической.

Answer 5

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

Answer 6

Рекурсия: Например: возьмите, например, ряд фибоначчи. чтобы получить номер фибоначчи, мы должны знать предыдущий. Таким образом, u будет выполнять операцию (то же самое) на каждом номере, меньшем заданного, и каждый из этих inturn вызывает тот же метод.

FIB (5) = Fib (4) + 5

FIB (4) = Fib (3) + 4 . . , т. Е. Повторное использование метода fib

Итерация циклическая, как если бы вы добавили 1 + 1 + 1 + 1 + 1 (итеративное добавление), чтобы получить 5 или 3 * 3 * 3 * 3 * 3 (итеративно умножая), чтобы получить 3^5.

Answer 7

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

Algorithms (4th Edition)