再帰関数を利用すると、 バックトラック法による探索をすることができます。 バックトラック法は、 「 深さ優先探索 」 とも言われています。 それは 「 １手ずつ手を進められるだけ進めて、 それ以上は無理であるということが解ると一手だけ戻ってやり直す。」 という方法です。

　 再帰関数によるバックトラック法のアルゴリズムを理解するためには、 山中和義 / 電脳遊戯団 さんが公開されている 「 自然数の分割 （ バックトラック法 ）.bas 」 というプログラムを勉強するのがいいと思います。
　　　　　http://www.urban.ne.jp/home/kz4ymnk/seminar/basic/index.html

　 以下に、 そのプログラムを記載します。 ただし、 アルゴリズムが解りやすいようにするために、 途中経過を PRINT するよう書き加えさせていただいております。

　 このプログラムを実行しますと、 p が深さを表し、 １つずつ深くなっていって、 それ以上は無理であるということが解ると一つだけ戻ってやり直していることが解ります。 たとえば、 L(5) に注目してください。 L(5) は 1 から 5 までのいろんな値を取っています。 では、 L(5) ＝ 3 に注目してください。 ΣL(4) の値がそれぞれ異なります。 こうして、 すべての可能性のあるケースが探索され条件を満たすかどうかの判定が行われていることがわかります。 それにしても、 再帰関数を考え出した人、 またそれを自由自在に操れる人はすごいなと思います。

※ 参照： 十進 BASIC ＞ 十進 BASIC＿パズル＆クイズ ＞ 同じ交差点を通らずにゴールするすべての場合の数