Стандарт ML: Итеративный против рекурсивного

Question

Я читаю ML для рабочего программиста и немного смущен различием автора между итерационным и рекурсивным. Я понимаю, что «рекурсивный» просто ссылается на функцию, которая называет себя. Любая функция, которая не является рекурсивной, является итеративной (где итеративный алгоритм обычно включает некоторый цикл).

Однако в этой книге автор скажет что-то вроде «к счастью, очевидное рекурсивное решение является итеративным». Поэтому мое понимание этих терминов, безусловно, отличается от того, как автор использует их.

Может кто-нибудь уточнить, где я не понимаю эти термины?

Спасибо, bclayman

Answer 1

Итерационный означает, что вы можете выразить это с петлей. Однако, вообще говоря, цикл является лишь частным случаем рекурсии. Например, в SML, петли

while A do B 

буквально определяется как синтаксический аббревиатура для рекурсивного определения

let fun loop() = if A then (B; loop()) else() in loop() end 

Вот почему «итеративный» не понимается как противоположность «рекурсивным», но как частный случай: некоторые рекурсивные определения являются итеративными, другие - нет. Более конкретно, это частный случай linear рекурсия, где рекурсивное определение вызывается не более одного раза.