Рекурсия - сложная задача!

[RomT24]

Привет всем!
У меня такая проблема - я очень плохо понимаю сущность понятия рекурсия - само определение безусловно знаю, а применять на практике - полный ступор.. Подскажите решение следующей задачи:

"Дано дерево глубины N, каждая внутренняя вершина которого имеет K(<10) непосредственных потомков (нумеруются от 1 до К)". Корень дерева имеет номер 0. Записать в текстовый файл с данным именем все возможные пути, ведущие от корня к листьям. Перебирать пути, начиная с "самого левого" и заканчивая "самым правым" (при этом первыми заменять конечные элементы пути). "

Вот такое вот непонятное мне условие (не то что решение!). Кто может, помогите решить (лучше сегодня)!

[Sazary]

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

И не сможете применять, если не начнете.

Как я понял, содержимое файла будет примерно таким (при N = 4)

0->1->1->1
0->1->1->2
0->1->1->3
...........
0->3->2->3
.....

В рекурсивной функции в цикле от 1 до K вызывать себя. При этом передавать номер текущей позиции.
Если текущая позиция = N+1, то записываем путь в файл и выходим из функции.

[RomT24]

Спасибо за объяснение, тем не менее мне очень стыдно, но... я мало что уяснил почему путь будет выглядеть 0111,0112 и 0113... 0323 и т.д при N=4? тогда чему равно К и где она используется? Не могли бы вы, так сказать, "визуально" объяснить мне условие? И почему позиция должна доходить до N+1, а не до N?

[Sazary]

Ну смотрите. N - глубина дерева. В нашей программе это фактически количество вызовов рекурсивной функции для определения одного из возможных путей.
А K - количество листьев. То есть при каждом вызове функции нужно обходить еще каждый лист.
Пусть N = 3, а K = 2.
В общем виде путь будет выглядеть как-то так:

0 -> # -> # -> #

0 - корень дерева. А # - вершины.

Заголовок функции навскидку будет выглядеть так:

procedure rec(tek : integer; s : string);

Здесь tek - глубина, которой мы уже достигли.
s - строка, в которую мы пишем путь.

И почему позиция должна доходить до N+1, а не до N?

Ну это зависит от того, как делать самый первый вызов функции.
Например, вызовем ее так:

rec(0,'');

Тогда условие выхода из функции будет tek = N

В самой функции нужно обойти все листья (перебрать все варианты).
То есть будет цикл от 1 до K. В этом цикле мы вызываем функцию (себя, рекурсивно).
Примерно так:
Str(i,strnum); { преобразуем номер листа в строку и пишем в numstr }

rec(tek+1, s + ' -> ' + strnum);

tek+1 - значит, что мы углубляемся.
Ну а

s + ' -> ' + strnum

передает путь, который уже успели сформировать + только что выбранная вершина.

--------------------------
На самом деле, ничего особо сложного тут нет. Главное - разобраться.

[RomT24]

Sazary, спасибо огромное, я немного разобрался! ничего если потом я вынесу на суд свой код при возможных неудачах?

[Sazary]

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

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

Так выносите, конечно