LINUX.ORG.RU
ФорумTalks

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

 ,


0

2

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

Как правильно называется такая рекурсия? Можно ли к ней применить оптимизацию хвостой рекурсии? Как называется эта рекурсия (если такое есть) в общем случае, в смысле есть ф-ий не две, а много?

Спасибо.

★★★★

Последнее исправление: nanoolinux (всего исправлений: 1)

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

Bad_ptr ★★★★★
()

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

Miguel ★★★★★
()

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

coderage
()
Ответ на: комментарий от coderage

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

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

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

nanoolinux ★★★★
() автор топика
Ответ на: комментарий от true_admin

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

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

nanoolinux ★★★★
() автор топика
Последнее исправление: nanoolinux (всего исправлений: 1)
Ответ на: комментарий от nanoolinux

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

coderage
()
Ответ на: комментарий от coderage

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

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

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

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

nanoolinux ★★★★
() автор топика
Ответ на: комментарий от nanoolinux

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

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

Arrest
()
Ответ на: комментарий от Arrest

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

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

nanoolinux ★★★★
() автор топика

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

andreyu ★★★★★
()
Ответ на: комментарий от andreyu

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

а так?

в одномерное

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

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

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

nanoolinux ★★★★
() автор топика
Ответ на: комментарий от olibjerd

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

coderage
()

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

косвенная

qulinxao ★★☆
()
Ответ на: комментарий от coderage

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

qulinxao ★★☆
()
Ответ на: комментарий от qulinxao

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

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

coderage
()
Ответ на: комментарий от coderage

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

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

qulinxao ★★☆
()
Ответ на: комментарий от qulinxao

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

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

coderage
()

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

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

yu-boot ★★★★
()
Ответ на: комментарий от yu-boot

2^9

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

+-+-+-+
|x|o|x|
+-+-+-+
|x|o|o|
+-+-+-+
|x|o|x|
+-+-+-+
кто здесь выиграл? или кроме того, я хочу распечатать развития игр для всех вариантов побед только крестиков? Так быть?

nanoolinux ★★★★
() автор топика
Ответ на: комментарий от nanoolinux

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

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

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

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

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

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

yu-boot ★★★★
()
Ответ на: комментарий от yu-boot

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

нет. 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 подкинул очень дофига ключевых слов, по которым можно найти нехилое количество полезной инфы по теме. Даже на вики хорошая статья есть. За что ему большое спасибо.

nanoolinux ★★★★
() автор топика
Ответ на: комментарий от nanoolinux

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

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

qulinxao ★★☆
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.