Есть ли способ избежать ненужной рекурсии?

Я отправил этот вопрос на CodeReview , но понял, что это вопрос не столько о Haskell, сколько об алгоритме.

Код Haskell можно найти в моем репозитории github , но я думаю, что код не так важен, как общая концепция.

По сути, программа вычисляет оптимальный первый набор ходов в игре Калаха (в шведском варианте ). Учитывается только первый «ход», поэтому мы предполагаем, что вы можете начать и что ничего с точки, с которой противник может двигаться, не вычисляется.

Доска Калахиhttp://www.graf-web.at/mwm/kalaha.jpg

Доска начинается с пустых магазинов и равного количества шариков в каждом горшке.

Вы начинаете свой ход с того, что выбираете не -пустой горшок на своей стороне, поднимаете все шарики из этого горшка, а затем перемещаетесь по доске, бросая один шарик при прохождении горшка. Если ваш последний шарик приземлится в магазине, вы получите еще один ход. Если вы приземлитесь в не -пустой, не -магазинный горшок, вы забираете все содержимое этого горшка и продолжаете. Наконец, если вы попадаете в пустой банк, ход переходит к противнику.

До сих пор я решал эту проблему, выбирая все возможные пути, а затем сортируя их по количеству шариков в магазине к концу. Путь означает начать с одного из ваших горшков, выполнить все необходимые действия -, поднять -и -переместиться -вокруг и посмотреть, попадете ли вы в магазин или в пустой горшок. Если вы приземлитесь в магазине, вы сможете продолжить, и теперь появляется столько новых веток, сколько не -пустых горшков на вашей стороне.

Проблема заключается в том, что если вы начинаете с пятью шариками в горшках, то это уже довольно много путей.Подпрыгните до шести, и у ghci закончится память.

Причина, по которой я не могу понять, как сделать это менее затратным, заключается в том, что я думаю, что каждый путь необходим во время вычислений. Хотя мне потребуется не более трех путей (лучших )из тысяч (или миллионов )сгенерированных, остальные нужно прогнать, чтобы увидеть, действительно ли они лучше, чем предыдущие.
Если один длиннее (, как правило, лучше ), то это хорошо, но дорого. Если он короче любого предыдущего пути, то программа все равно должна была вычислить этот путь, чтобы найти это.

Есть ли способ обойти это или вычисление всех путей необходимо по определению?