Рекурсия

[pram]

Помогите, пожалуйста, понять рекурсию на след. примере..

<rec> <= [ <rec> X <rec> YY <rec> | <rec> YY <rec> X <rec> ]

Это EBNF...
[] означает опция
| означает выбор из двух альтернатив
Ответы могут быть следующими: XYY, YYX, XYYYYX, XXYYYY.

Т.е. получается, что если мы выбираем сначала левый вариант:
<rec> X <rec> YY <rec>, то происходит следующее:
Вызывается например первая <rec> в списке два раза, по ее окончании, выдается "X" и мы заходим во вторую <rec>.. а дальше у меня путаница начинается, как же это можно себе представить наглядно?

Спасибо за любой совет!!

[p51x]

Тут ничего не вызывается. EBNF - это описание.

<rec> X <rec> YY <rec>, то происходит следующее:
Вызывается например первая <rec> в списке два раза, по ее окончании, выдается "X" и мы заходим во вторую <rec>.. а дальше у меня путаница начинается, как же это можно себе представить наглядно?

Ничего не происходит. Это говорит, что rec имеет формат *X*YY*, где на месте * стоит rec, который имеет формат... и т.д.

[Plague]

Нарисуйте дерево!
Дерево рекурсивных вызовов.

[pram]

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

Тут ничего не вызывается. EBNF - это описание.


Ничего не происходит. Это говорит, что rec имеет формат *X*YY*, где на месте * стоит rec, который имеет формат... и т.д.

Я прекрасно представляю себе, что такое EBNF. "Вызывается" можно было поместить мной в кавычки, но не думал, что так к словам можно придираться. И происходит здесь многое. И мне нужно понять, какой результат этого описания является возможным, а какой нет. Например, описание
<rec> <= | X <rec> YY
дает возможность записать такие элементы XXX YYYYYY. И используется здесь рекурсия, но данный пример я себе хорошо представляю, а вот вышеуказанный нет. Ваше объяснение, к сожалению, крайне непонятно, но спасибо за попытку.

[pram]

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

Нарисуйте дерево!
Дерево рекурсивных вызовов.

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

[p51x]

Например, описание
<rec> <= | X <rec> YY
дает возможность записать такие элементы XXX YYYYYY. И используется здесь рекурсия, но данный пример я себе хорошо представляю, а вот вышеуказанный нет.

Только они ведь ничем не отличаются...

[pram]

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

Только они ведь ничем не отличаются...

<rec> <= [ <rec> X <rec> YY <rec> | <rec> YY <rec> X <rec> ]
--> YYX возможно

<rec> <= | X <rec> YY
--> YYX невозможно, а значит данные описания не эквивалентны.

[p51x]

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

[Pavia]

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

Помогите, пожалуйста, понять рекурсию на след. примере..

<rec> <= [ <rec> X <rec> YY <rec> | <rec> YY <rec> X <rec> ]

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

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

<rec> <= | X <rec> YY

Этот гораздо лучше.

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

<rec> <= | X <rec> YY
дает возможность записать такие элементы XXX YYYYYY.

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


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

[Pavia]

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