ねえ、私は次の問題に悩まされていて、正しい機能を思い付くことができないようです.
正の整数 k が与えられたとき、積 k を計算する再帰関数を書きます。
プログラムは通常、メモリがなくなるまで実行されます。これが私の方法です:
(define (fraction-product k)
(if (= k 0)
0
(* (- 1 (/ 1 (fraction-product (- k 1)))))))
事前に助けてくれてありがとう...
最初に小さなケースを手作業で行います。
コーディングしようとせずに、答えがどうあるべきかを手で計算します。
この種の問題を行う前に、少なくとも 3 つの具体的な例を手元に用意しておく必要があります。これは、混乱を解消するのに役立つだけでなく、実際のコードに到達する際の健全性テスト ケースとしても役立ちます。
(fraction-product 1)と(fraction-product 2)の間で手計算した答えの間に関係はありますか? (fraction-product 2)と(fraction-product 3)の間はどうですか?
(fraction-product 0)について心配する必要がありますか? 問題文を確認してください。
このような問題が発生した場合は、コードに直行しないでください。最初に小さな例を手作業で行います。答えがどうあるべきかを計算します。プログラムが実際に計算しようとしていること、およびそれを機械的に実行する方法について直感を働かせるのに役立ちます。
時間があれば、How to Design Programsなどの本を参照してください。このような種類の関数を設計するための体系的なアプローチが説明されています。
基本ケースを間違えました。isの場合k
は1
、return-を返す必要があります。再帰的に乗算する場合は、数値に達し1
たときに再帰が停止することを確認する必要があります。乗算すると、結果は常にになります。1
0
0
再帰呼び出しも誤っています(- 1 (/ 1 k))
。再帰の結果を乗算する必要があることに注意してください。次のようなものを試してください。
(define (fraction-product k)
(if (<= k 1)
1
(* (- 1 (/ 1 k))
(fraction-product (- k 1)))))
@Axioplaseの回答で示唆されているように、同じプロシージャは、末尾再帰を使用して一定のスタックスペースを使用するように記述できます。再帰呼び出しは、プロシージャが戻る前に最後に実行されるため、末尾位置にあります。
(define (fraction-product k)
(let loop ((acc 1)
(k k))
(if (<= k 1)
acc
(loop (* acc (- 1 (/ 1 k))) (- k 1)))))
そして、楽しみのために、同じ手順を次のように簡単に記述できることを理解するのは簡単です。
(define (fraction-product k)
(/ 1 k))
製品の引数は何ですか? 1つしかありません!したがって、製品は役に立たない(* n) == (* n 1) == n
。これにより、アルゴリズムが意図したとおりに動作しないことがすぐにわかります。
このようなバグを見つけるための良い戦略は、関数のすべてのパラメーターを別々の行に記述することです…</p>
また、 when k == 0
,(fraction-product 0)
は 0 を返します。次に、おそらくやり直したいことではないことを
(fraction-product 1)
計算します…</p>(/ 1 (fraction-product 0)) == (/ 1 0)
実際には、分数の積とはまったく異なるものを計算したいようです...むしろ再帰的な分数です (そのようなものの名前を忘れました)。
とにかく、(1 - 1/2) * (1 - 1/3) * ... * (1 - 1/k)
あなたは次のようなことをすることができます
(define (f-p k)
(define (aux n) (- 1 (/ 1 n)))
(let loop ((i 2))
(if (> i k)
1 ;; base case: multiply by 1, i.e. "do nothing"
(* (aux i) (loop (+ i 1))))))
これは一定のスタック スペースを使用するように最適化できますが、それはポイントではありません。