Решение упражнения 1.9 из SICP

17 August, 2007 (20:02) | Решения упражнений

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

Первый процесс породит такую последовательность:

(+ 4 5)
(inc (+ 3 5))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8 )
9

Очевидно, что процесс строит последовательность отложенных операций декремента, линейно растущую с числом операций. Следовательно первый процесс - линейно-рекурсивный.

А вот что порождает второй процесс:

(+ 4 5)
(+ (dec 4) (inc 5))
(+ 3 6)
(+ (dec 3) (inc 6))
(+ 2 7)
(+ (dec 2) (inc 7))
(+ 1 8 )
(+ (dec 1) (inc 8 ))
(+ 0 9)
9

Здесь нет отложенных операций, то есть процесс линейно-итеративный.

Comments

Comment from thror
Date: February 14, 2008, 11:47 pm

Подавляющее боьшинство подобных вещей могут быть построены автоматически. См. так же упражнение 1.14 про размен монет.

(define (dec x)
  (- x 1))

(define (inc x)
  (- (dec (- x))))

(define (+ a b)
  (if (= a 0)
      b
      (inc (+ (dec a) b))))

(define (+ a b)
  (if (= a 0)
      b
      (list 'inc (+ (dec a) b))))

(define (+ a b)
  (if (= a 0)
      b
      (+ (dec a) (inc b))))

(define (+ a b)
  (display (list '+ a b))
  (newline)
  (if (= a 0)
      b
      (+ (dec a) (inc b))))

–thror

Comment from Sergey Khenkin
Date: February 15, 2008, 9:34 am

Безусловно, могут.
И все же на начальном этапе очень полезно строить такие вещи вручную, вообще не касаясь интерпретатора.
Хотя потом, конечно же, можно себя проверить.

Write a comment