我修改了SICP中count-change
函數的代碼,以便在函數遞歸時它將顯示一對。這對的形式是"(cc a k)" -> "(cc a (- k 1))"
或"(cc a k)" -> "(cc (- a (d k)) k)"
,我的目標是建立一個DOT文件來顯示使用GraphViz的樹狀遞歸。如何使用方案宏來顯示評估樹
下面是一個例子的圖像,從下面的代碼生成:
這裏的方案的代碼:
; Count Change
(define (count-change amount)
(cc amount 5))
(define (cc amount kinds-of-coins)
(begin
(cond ((= amount 0) 1)
((or (< amount 0) (= kinds-of-coins 0)) 0)
(else (+
(begin
(display "\"")
(display `(cc ,amount ,kinds-of-coins))
(display "\"")
(display " -> ")
(display "\"")
(display `(cc ,amount ,(- kinds-of-coins 1)))
(display "\"")
(display "\n")
(cc amount (- kinds-of-coins 1))
)
(begin
(display "\"")
(display `(cc ,amount ,kinds-of-coins))
(display "\"")
(display " -> ")
(display "\"")
(display `(cc ,(- amount (first-denomination kinds-of-coins)) ,kinds-of-coins))
(display "\"")
(display "\n")
(cc (- amount (first-denomination kinds-of-coins)) kinds-of-coins)
)
)
))))
; first-denomination takes the number of kinds of coins and returns the denomination of the first kind
(define (first-denomination kinds-of-coins)
(cond ((= kinds-of-coins 1) 1)
((= kinds-of-coins 2) 5)
((= kinds-of-coins 3) 10)
((= kinds-of-coins 4) 25)
((= kinds-of-coins 5) 50)))
(count-change 11)
原始代碼是here。
我已閱讀關於方案宏,我認爲他們可以解決這個問題,允許我在begin
語句中用'wrap'調用(cc。)語句來顯示遞歸時正在發生的事情。
這怎麼可以用Scheme宏來完成?
注意:我知道我的圖像是不準確的,我需要找到一種使節點不同的方法,以便圖形是一棵樹,而不僅僅是一個DAG。但是,這超出了這個問題的範圍。
對於實現,我使用MIT/GNU計劃。這比我有的更好,我喜歡打印是在它自己的功能。實際上,這可以通用化,以便'cc'是一個通用函數,這樣我可以在其他函數上重用它! – tlehman 2013-02-11 05:49:03
我沒有使用本地函數,但是我做了類似於你所建議的[這裏](https://github.com/tlehman/sicp-exercises/blob/master/count-change-verbose.scm) 。我正在努力使它獨立於函數的arity。 – tlehman 2013-02-11 06:16:14
我通過使用節點的標籤來解決這個問題,因此'rrllr'會向右,左,左,右移動。 [詳情和圖片在這裏](http://tobilehman.com/blog/2013/04/07/visualization-of-sicp-exercise-1-dot-14/) – tlehman 2013-05-15 03:08:07