Способы разменять монеты

Хитроумный алгоритм по размену монет из первой главы SICP. Мне потребовалось значительное время, чтобы понять как он работает и воспроизвести его:

#
# Число способов разменять n центов монетами по 1, 5, 10, 25 и 50 центов.
# 

; Доступные монеты
(set 'монеты '(1 5 10 25 50))

; Число разменов n центов с помощью c монет.
(define (размены n (c 5))
  (cond ((< n) 0)
        ((= n) 1)
        ((= c 1) 1)
        (true (+ (размены n (- c 1))
                 (размены (- n (монеты (- c 1))) c)))))

Это воссозданный мной алгоритм из книжки. Вначале же я сделал иначе: считал все возможные методы размена, потом через unique отбирал уникальные, потом через memoize добивался терпимой скорости. Тоже работало, плюс кроме числа способов размена я видел в списке ещё и сами способы.

Но решение из книжки, конечно, красивее.

Кстати, в самой книжке алгоритм реализован, на первый взгляд, примерно так же, но там есть слова: «на то, чтобы получить ответ 292 уйдёт какое-то время». В реальности время выполнения процедуры на моём компьютере — 0,3 миллисекунды.

То ли эта фраза писалась в семидесятые года, то ли newLISP гораздо круче чем Scheme.

PS: Разменять доллар можно 292 способами. Способов разменять 10 долларов уже 800 тысяч.

PPS: Те же яйца, но с печатью дерева.

(define (размены n (c 5))
  (print "Р" n " (" c "): ")
  (cond ((< n) (println 0) 0)
        ((= n) (println 1) 1)
        ((= c 1) (println 1) 1)
        (true (println "Р" n " (" (- c 1) ") + Р" (- n (монеты (- c 1))) " (" c ")")
              (+ (размены n (- c 1)) (размены (- n (монеты (- c 1))) c)))))