Рассмотрим характер рекурсии на примере очень простой функции обработки строк, которая трансформирует каждое  A в B :

  Fab {
     A e1 = B <Fab e1>;
     s2 e1 = s2 <Fab e1>;
      = ; }

Будучи написанным и исполняемым в РЕФАЛе, это определение является итеративным. В самом деле, расширение вызова функции включает не более одного функционального вызова; символы накапливаются в поле зрения как части окончательного результата, а накопления функциональных вызовов не происходит. И все же само определение рекурсивно по форме, а не итеративно. Если записать полностью аналогичное определение в Лиспе:

  (define (fab x)
     (cond ((null x) nil)
        ((equal (car x)(quote a))
            (cons (quote b) (fab (cdr x))))
           (T (cons (car x)(fab (cdr x))))
     ))

то оно определенно является  рекурсивным, но не остаточно-рекурсивным: отложенные вызовы функции-конструктора cons накапливаются в памяти до тех пор, пока значение аргумента функции fab не становится равным nil (пустым).

(c) Турчин В.Ф.