Рекурсия

[pram]

Сообщение от p51x

Я не про их "равенство" друг другу, а про подход/построение и т.д. И если вы понимаете, как работае те второе, то и первое работает абсолютно также.

Я задаю себе тот же вопрос, но почему-то мне тяжело понять второе описание, так как видимо много рекурсий..

[pram]

Сообщение от Pavia

Это плохой пример, так как он не входит в классификацию Хомского.
Этот гораздо лучше.

Тут явно ошибка.

pram Какие у вас есть навыки в работе с рекурсией? Какие задачи уже решали?
а) Фибоначчи
б) размен денег монетами
в) обход в ширину
г) обход в глубину
д) проверка скобок на правильность
е) проверка трёх разных видов скобок на правильность
ж) регулярные выражения.

Спасибо большое за Ваш ответ!
Не подскажите почему ошибка в данном описании?
<rec> <= | X <rec> YY
--> XXX YYYYYY

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

А это описание состовлял не я.. а преподаватель.
<rec> <= [ <rec> X <rec> YY <rec> | <rec> YY <rec> X <rec> ]
Поэтому пытаюсь понять, как именно получаются элементы XYY, YYX, XYYYYX, XXYYYY.

[pram]

Сообщение от Pavia

П.С. Забыл спросить вас интересует генерация последовательностей по языку или распознавание входной последовательности?

Меня интересует и то и другое.. так как вопросы будут и те и другие..

[Dench]

Фига-се, я в тему зашел.
Думал тут про стандартное использование рекурсии.
Ан, нет! Формулы понять могу, - На код положить часть могу.
И как всегда никому ничего не нужно(((.

[p51x]

Поэтому пытаюсь понять, как именно получаются элементы XYY, YYX, XYYYYX, XXYYYY.

XYY -> [<rec> X <rec> YY <rec>]
YYX -> [<rec> YY <rec> X <rec>]
XYYYYX -> [<rec> X <rec> YY [<rec> YY <rec> X <rec>]]
XXYYYY -> [<rec> X [<rec> X <rec> YY <rec>] YY <rec>]

[pram]

Сообщение от p51x

XYY -> [<rec> X <rec> YY <rec>]
YYX -> [<rec> YY <rec> X <rec>]
XYYYYX -> [<rec> X <rec> YY [<rec> YY <rec> X <rec>]]
XXYYYY -> [<rec> X [<rec> X <rec> YY <rec>] YY <rec>]

Спасибо большое за Ваш ответ, но меня видимо сильно сбивает с толку в разных местах появляющаяся рекурсия.. вот, чтобы далеко никуда не ходить, начать с Вашего первого примера:

XYY -> [<rec> X <rec> YY <rec>]

ведь здесь также возможно и XXYYYY. И разве нельзя просто написать
[X <rec> YY]

Какую функцию все-таки выполняют первая и последняя <rec>? Вот если мы представим, что это настоящая программа и <rec> это рекурсивная функция, которая вызывается два раза и после этого прерывается каким-либо условием. В стеке у нас к этому моменту два вызова с YY.

Т.е., если мы берем:
[X <rec> YY]
и вызываем <rec> один раз, то имеем XYY. Если если вызываем два раза, то имеем XX, потом из стека YYYY, т.е. получается XXYYYY.

Увеличиваем наше описание на еще еще две "рекурсивные функции" (т.е. слева и справа
[<rec> X <rec> YY <rec>]

Что нам это дает и как это можно в двух словах понять?

[p51x]

И разве нельзя просто написать
[X <rec> YY]

Какую функцию все-таки выполняют первая и последняя <rec>?

[X <rec> YY] не даст YYXXYY, а [<rec> X <rec> YY] уже даст.

Что нам это дает и как это можно в двух словах понять?

Именно то, что записано. На данное место мы можем поставь <rec>.

Давай по другому - может так дойдет:
Начнем без рекурсии. Вы понимаете, чем отличается *X*Y и X*Y?

[pram]

Сообщение от p51x

[X <rec> YY] не даст YYXXYY, а [<rec> X <rec> YY] уже даст.


Именно то, что записано. На данное место мы можем поставь <rec>.

Давай по другому - может так дойдет:
Начнем без рекурсии. Вы понимаете, чем отличается *X*Y и X*Y?

Только ведь *в начале, но я не знаю, что Вы подразумеваете под *..

[p51x]

Просто *.

Дальше можете взять, что под * понимается любая цифра - в данном случае вы понимаете, чем отличается *X*Y и X*Y? Из какого получится 1X0Y, а из какого нет?

[pram]

Сообщение от p51x

Просто *.

Дальше можете взять, что под * понимается любая цифра - в данном случае вы понимаете, чем отличается *X*Y и X*Y? Из какого получится 1X0Y, а из какого нет?

Да, это понятно, т.е.
*X*Y и X*Y?
1X0Y, а X0Y

Т.е. если мы возьмем например:
[<rec> X [<rec> X <rec> YY <rec>] YY <rec>]
--> 1X1X0YY0YY0

Я правильно понял?