SICP - Рекурсивный или итеративный процесс?

Question

Я использую книгу SICP, и я борюсь с концепциями рекурсивного итеративного процесса. На вопрос 1.17 они спрашивают:

Упражнение 1.17. Алгоритмы возведения в этот раздел основаны на выполнении возведения в степень посредством повторного умножения. Аналогичным образом можно выполнить целочисленное умножение с помощью повторного добавления. Следующая процедура умножения (в которой предполагается, что наш язык может только добавить, не умножать) аналогична процедуре EXPT:

(define (* a b) 
    (if (= b 0) 
    0 
    (+ a (* a (- b 1))))) 

Этот алгоритм принимает ряд шагов, линейна в б. Теперь предположим, что вместе с добавлением мы включаем операции double, которые удваивают целое число, и уменьшают вдвое, разделяя (четное) целое на 2. Используя их, создайте процедуру умножения, аналогичную быстрому expt, который использует логарифмическое число шагов.

(Источник: https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.4)

Я сделал следующий код, который, как представляется, право:

(define (* a b) 
    (cond ((= b 1) a) 
     ((even? b) (* (double a) (halve b))) 
     (else (+ a (* (double a) (halve (- b 1))))))) 

Если использовать след, встроенный в функции отладки в доктора Ракетка, inputing 343 и 799 Я получаю:

(require racket/trace) 
(trace *) 
(* 343 799) 

>(* 343 799) 
> (* 686 399) 
> >(* 1372 199) 
> > (* 2744 99) 
> > >(* 5488 49) 
> > > (* 10976 24) 
> > > (* 21952 12) 
> > > (* 43904 6) 
> > > (* 87808 3) 
> > > >(* 175616 1) 
< < < <175616 
< < < 263424 
< < <268912 
< < 271656 
< <273028 
< 273714 
<274057 
274057 
> 

Я смущен. Процесс, который я создал, имеет рекурсивное определение, но, похоже, имеет рекурсивный характер и итеративный характер. Я ошибаюсь? Может ли процесс быть итеративным и рекурсивным?

Я вижу рекурсивную природу с дизайном дерева при ее отладке. И я вижу итеративный характер, так как я использую переменную/параметр «a» как переменную состояния. Я что-то неправильно понял?

Answer 1

Процесс, показанный в вашем коде, является рекурсивным - вы можете видеть, что при каждом вызове в части else выполняется еще одна операция: добавление. Как правило, итеративный процесс передает ответ в качестве параметра (аккумулятор ) таким образом, что рекурсивный вызов находится в хвосте позиция - то есть это последнее, что мы делаем, без остающихся отложенных операций.

В вашей трассе стека очевидно, что происходит рекурсивный процесс, вызовы процедуры * складываются до определенной точки, а затем начинают возвращаться - это похоже на треугольник. Сравните это с этим, действительно итеративным умножением; здесь мы не видим форму треугольника при выполнении trace, и процедура проходит в постоянном объеме пространства:

(define (mul a b) 
    (define (iter count acc) 
    (if (zero? count) 
     acc 
     (iter (- count 1) (+ acc a)))) 
    (iter b 0)) 

(trace mul) 
(mul 343 799) 

>(mul 343 799) 
<274057 
274057