Парная рекурсия? Или как это называется?

есть такой термин mutual recursion
перевод слова mutual — посмотри в словаре

Взаимная рекурсия. Хвостовая - оптимизируется (собственно, оптимизация хвостовой рекурсии - неправильное название, правильно - оптимизация хвостовых вызовов, tail-call optimization).

код потом покажи :)

В моих книгах это называлось косвенной рекурсией.

Авторы учебников по рекурсии на ЛОРе!

http://pastebin.com/4Qpme1Eg

только там ещё багов полно.

Рекурсия - как нож лезвие, им можно резать, а можно пораниться. Я не до конца понимаю, зачем из одной функции вызывать другую в данной задаче. На мой взгляд логичнее вызывать фукнции последовательно в цикле (завершение при заполнении поля/победе). Если только для обучения. Надеюсь, что это так.

Думаю существует целый класс задач, которые решать таким способом намного проще и быстрее.

как нож лезвие

C тоже как нож лезвие. Предлагаешь выкинуть С?

Эх, я думал там какой-нить хаскель :(

Хаскель не знаю. На эрланге можно всё тупо в лоб переписать, но мне в лом.

Хотя попробую.

Из вашего сообщения не ясно, какой способ вы считаете «проще и быстрее». Рекурсия может легко породить неочевидные ошибки (те же утечки), в то время, как в цикле все предельно прозрачно.

проще и быстрее

проще придумать, быстрее заимплементировать.

Рекурсия может легко породить неочевидные ошибки (те же утечки), в то время, как в цикле все предельно прозрачно.

Хахаха! Да именно так, бро.

Я тоже был разочарован.

Рекурсия может легко породить неочевидные ошибки (те же утечки)

С тебя пример.

Да, и еще tail call нельзя оптимизировать.

Почему?

Вообще в сях это опциональная фича, там оптимизация и не подразумевается вовсе.

Потому что ты рекурсивно вызываешься в цикле. Для TCO нужно продолжать рекурсию последней исполняемой вещью в функции.

Да, я знаю, но это к тому, что даже если бы и подразумевалась, то здесь она бы не работала.

вызываеться в цикле

Да, я что-то сам не подумал.

А не проще ли использовать троичную систему счисления и преобразовать двумерное поле в одномерное? Зачем тут нужно рекурсия?

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

а так?

в одномерное

я так и сделал вообще-то.

Зачем тут нужно рекурсия?

в образовательных целях.

Авторы учебников по рекурсии на ЛОРе!

Ну почему стразу учебников. Может он всякий фикшн пишет.

Гугл есть, сами ищите, или думайте головой.

Вы очень интересный собеседник.

Прямо как Душкин ;)

Я дико извиняюсь - был пьян и зол. Завтра постараюсь найти, когда голова перестанет болеть. :)

топик не читал.

косвенная

гугли максимин

либо минимакс(однако этот термин более распространён и вульгаризирован)

конкретней вот это

http://ru.wikipedia.org/wiki/Альфа-бета_отсечение

А зачем она тут вообще?.. Есть какая-то причина, делающая использовании рекурсии выгодным в данной задаче?

То есть если это игра (крестики-нолики), то как правило игровой движок слегка по-другому выглядит: подгрузка всего, а потом в бесконечном цикле, жрущим события ввода, обработка логики, ввода и рендер.

ответ у мартина гарднера в крестиках-ноликах про самообучающийся автомат из спичечных коробков и вкусных нямок и слуги любителя этих нямок.

челу в лом иметь полное решение и он использует рекурсию(а конкретно альфа-бета отсечения)(если совсем просто то исчерпывающий(ибо дерево мелькое) анализ на каждой позиции без хранения ибо усложняет программу :) а cpu-time- дёшево) для оптимальной игры компом.

самообучающийся автомат из спичечных коробков и вкусных нямок и слуги любителя этих нямок

Взорвало мозг :) Но спасибо, ссылку почитаю.

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

Тебе нужна статистика кто у кого будет чаще выигрывать или просто проанализировать все возможные варианты? Если все варианты - просто for от 1 до 2^9, не?

2^9

Нет. Не все игры заканчиваются заполнением всех полей. Например

+-+-+-+
|x|o|x|
+-+-+-+
|x|o|o|
+-+-+-+
|x|o|x|
+-+-+-+

Взорвало мозг :)

почитай про рекурсивный вызов лямбда ф-и например.

Нет. Не все игры заканчиваются заполнением всех полей.

Ну так у тебя так и будет. Потом делаешь проверку на «возможность существования» получившейся ситуации в соответствии с правилами, а потом ещё одну, на «кто выиграл».

кто здесь выиграл?

Зависит от правил, ничья или крестики, ибо всегда ходят первыми.

или кроме того, я хочу распечатать развития игр для всех вариантов побед только крестиков?

Просто добавляются условия. Можно конечно «рандомно сходили крестики, проверка кто выиграл, рандомно сходили нолики, проверка кто выиграл», но через какое-то время у тебя ситуации начнут повторяться, не?

ничья или крестики,

нет. x(0,0), o(1,0), x(2,0), o(1,1), x(0,1), o(1,2) и нолики выигрывают.

Просто добавляются условия. Можно конечно «рандомно сходили крестики, проверка кто выиграл, рандомно сходили нолики, проверка кто выиграл», но через какое-то время у тебя ситуации начнут повторяться, не?

No. No, no, no. NOOOOOOOOO! Вот это то, что я пытался донести здесь Парная рекурсия? Или как это называется? (комментарий) товарищу coderage. Вместо тупого и простого как валенок рекурсивного обхода дерева всех возможных ходов начинается выдумывание всяких костылей, основаных на неверных утверждениях и догадках. И после этого мне ещё и пишут, что «рекурсия - нож, можно порезаться» или «возможны утечки, лучше циклами».

Поднимите уже свои приплюснутые головы и начните думать шире наконец! Освойте уже хоть что-то вне своего императивного мирка! Я конечно не говорю, что я крутой фукциональщик, сам только на плюсах и пишу, но надо развиваться, чуваки.

Кстати, тов. qulinxao подкинул очень дофига ключевых слов, по которым можно найти нехилое количество полезной инфы по теме. Даже на вики хорошая статья есть. За что ему большое спасибо.

достаточно дефиниция Y-комбинатора на любом языке поддерживающем функции как «граждан первого класса»

и задание падавану «понять и обьяснить (как таблицу умножения чтоб от зубов отскакивало)» - говорят что 95% на этом этапе отсеиваются и не становятся джедаями