Решение упражнения 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

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

Comment from filimon
Date: September 4, 2012, 3:29 pm

По-моему в объяснении задачи опечатка (если, конечно, я сам правильно понимаю происходящее)). Вы написали, что процесс строит последовательность отложенных операций ДЕкремента. Но по-моему откладываются операции ИНкремента. Если я ошибаюсь, то, если не затруднит, растолкуйте, что именно я понял не так.

Write a comment