Schemeについての問題

質問

今大学でSchemeについて学んでいるのですが、そこで出た問題がわからなくて困っています。
よければ、教えていただけないでしょうか。
問題は以下の通りです。

問１ 次に示すScheme プログラムについて以下の問に答えよ。
(define (subtree? t1 t2)
(cond ((atom? t1) (eq? t1 t2))
(#t (cond ((atom? t2) #f)
(#t (or (and (subtree? (car t1) (car t2))
(subtree? (cdr t1) (cdr t2)))
(or (subtree? t1 (car t2))
(subtree? t1 (cdr t2)))))))))
関数subtree?は二つのS 式(S 表現) t1, t2 を入力とし、真偽値(#t あるいは #f) を返す関数である。
関数subtree?が真(#t) を返すための必要十分条件は何であるか答えよ。
また、関数subtree?が実際そのような関数であることをS 式に関する帰納法を用いた議論によって示せ。

考えたのですが、わからなくて。こんな質問してしまって申し訳ないです。
よければよろしくお願いしますm(_ _)m

回答No.1

sakusaker7

> 考えたのですが、わからなくて。こんな質問してしまって申し訳ないです。
こういう書き方するとここでは禁止されている丸投げにとられますよ。
まあ実際そうなのかもしれないけど。

> (define (subtree? t1 t2) ← 関数名が subtree?

> (#t (or (and (subtree? (car t1) (car t2))
> (subtree? (cdr t1) (cdr t2)))
> (or (subtree? t1 (car t2))
> (subtree? t1 (cdr t2)))))))))

subtree? の定義の中で subtree? を呼び出している → 再帰
ってのはわかってますか?
で、再帰を使った定義の場合は停止条件があるはずです。で、それは

> (cond ((atom? t1) (eq? t1 t2))
> (#t (cond ((atom? t2) #f)

この辺。
t1 が atom であり、かつ eq? t1 t2 が真なら関数自体の戻り値も真です。
t1 が atomでなくて、かつ t2が atom だったら関数自体の戻り値が偽になります。
上記二つの条件が満たされていないケースなら、再帰呼び出しを使って
与えられたS式の検査を進めます。

適当なS式を作って、デバッガで追いかけるなり図に描くなりして
再帰の底から戻ってくる(停止条件)のはどういうときなのかに注意して
追いかけてみてくださいな。

> また、関数subtree?が実際そのような関数であることをS 式に関する帰納法を用いた議論によって示せ。

こっちは、S式とはどういうものかの定義をよーく考えた上で、subtree? の
停止条件を踏まえてみれば見当がつくはず。

んじゃがんばってくださいな。