id:hyukiさんよりコメントを頂きました。

段数が多くなったときは、二つの解法に違いは生じるでしょうか？

階段クイズ – 週記くらい%28BTS開発記%29のコメント欄

結城さん直々にクイズその弍を貰いました。ありがとうございます。

力技版を answer-1 という関数名で定義して、模範解答版を answer-2 という関数名で定義しました。

結果計測するまでもなく、力技版は、階段を40段にしたくらいで相当遅くなっていました。模範解答版は、まだ余裕がありました。

以下、40段の結果

CL-USER> (compile 'answer-1)
ANSWER-1
NIL
NIL
CL-USER> (compile 'answer-2)
ANSWER-2
NIL
NIL
CL-USER> (time (answer-1 40))
Real time: 112.9799 sec.
Run time: 110.846924 sec.
Space: 2380846872 Bytes
GC: 3429, GC time: 16.581068 sec.
165580141
CL-USER> (time (answer-2 40))
Real time: 19.153519 sec.
Run time: 18.693169 sec.
Space: 192 Bytes
165580141
CL-USER>

やはり、力技版は全ての組合せを試している(40階層のツリーをくまなく渡り歩いている)ので計算量が増えていることから、処理時間が長くなっているのはわかるんですが、Spaceが異常に多い(2.3G!)のは、letのレキシカル環境がlabelsで再帰のたびにコピーされまくるからかな？ちょっと今の理解力では解明できないので、また調べてみようと思います。

模範回答版は、自分で階段の登り方のパターン数を数えるのではなく、1段の場合と2段の場合に帰結するようにしているので、最低限の計算量で答が求められる様子。末尾再帰ではないけど、再帰自体の回数も力技版とは比にならないくらい少ないはずです。

しかし、力技版がスペースを使いまくっているのをどうやって調べればいいんだろう。。

一応、テストに使った関数を貼っておきます。

;力技版
(defun answer-1 (step-count)
(let ((way-count 0))
(labels ((rec (n)
(if (zerop n)
(incf way-count) ;reached.
(loop for i from 1 to 2
until (< n i)
do (rec (- n i))))))
(rec step-count)
way-count)))
;模範解答版
(defun answer-2 (step-count)
(or (plusp step-count)
(error 'step-count-msut-plus-value))
(case step-count
(1 1)
(2 2)
(otherwise (+ (answer-2 (- step-count 2))
(answer-2 (- step-count 1))))))