3

フィボナッチ再帰のツリー再帰実装などの関数が与えられた場合、次のような式の評価の各ステップをどのように示すことができ(fib 5)ますか?

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1)
                 (fib (- n 2))))))

たとえば、次のように出力したいと思います。

(fib 5)

(+ (fib 4) (fib 3))

(+ (+ (fib 3) (fib 2)) (+ (fib 2) (fib 1)))

(+ (+ (+ (+ (fib 1) 0) (fib 1) (+ (fib 1) 0)) (+ (+ (fib 1) 0) (fib 1)))

(+ (+ (+ (+ 1 0) 1 (+ 1 0)) (+ (+ 1 0) 1))

準引用符を使用すると、次のように式を部分的に評価できることを知っています。

`(+ ,(* 3 4) (- 0.1 2))   ; evaluates to -┐
(+ 12 (- 0.1 2))          ;          <----┘

ただし、これを使用して評価の各ステップを示すことはできませんでした。Peter Norvig のlis.pyのようなスキーム インタープリターを変更できることはわかっていますが、言語自体の中でそれを行う方法が必要です。これどうやってするの？

4

1 に答える 1

5

つまり、このように？

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else `(+ ,(fib (- n 1))
                  ,(fib (- n 2))))))

例えば：

(fib 5)
=> '(+ (+ (+ (+ 1 0) 1) (+ 1 0)) (+ (+ 1 0) 1))

もちろん、上記は評価の最終結果のみを返します。Racket のような組み込みのステッパーを使用すると、各中間ステップを確認できます。少しハウツーについては、この回答を参照してください。これはたまたまフィボナッチ関数も示しています。

于 2013-02-09T16:42:18.153 に答える