Не только слово XTREE , все слова с нечетным количеством букв подходят для "ёлочной" рекурсии. Все буквы слова расположены в форме ёлки.

Для слова XTREE получается след. ёлка :


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

Ответьте на вопрос рекурсивным математическим определением функции XFire и реализуйте в паскале.

Помогите, пожалуйста, разобраться. Не понимаю вообще как решать задачу.
В какую сторону идти?

Для начала почитать что-нибудь про рекурсию.
Этого достаточно.

Для начала я почитала. И тем не менне непонятно... Я понимаю, что это моя проблема в непонимании. Но прошу помочь как-нибудь..

И чего ты хочешь?
Чтобы тебе пересказали то же самое, но своими словами?

Я не знаю. Просто объяснить как рекурсия работает на этом примере.

Почему именно на этом? Тебе уже объясняли, как работает рекурсия, неоднкратно. Ты говоришь, что читала, но не поняла. Какой смысл здесь "растекаться мыслью по древу" (С)? Если ты не поняла там - какой шанс у тебя понять здесь?

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

Что такое рекурсия теоретически я понимаю. Понимаю как работают примеры вычесления факториала, послед. Финабоччи и возведения в степень. Дальше дело не идет(

Расскажи.
Отсюда и "начнем плясать".

по идее Wegs(Wort) := Wegs(wort)-3+Wegs(wort-2)
Wegs(3) = 3

*Wegs- кол-во путей
*Wort - кол-во букв

Непонятно.
Wegs(Wort) := Wegs(Wort)-3+Wegs(Wort-2) - это не рекурсивное математическое определение, так как справа тоже стоит Wers(Wort), который мы и пытаемся определить.

тогда я совсем не поняла(
Wegs := Wegs(Wort)-3+Wegs(Wort-2)

Хорошо, что значит?
i := i+1;

значение увеличивается на единицу...

Вот то же самое происходит и с функцией: она вызывает сама себя с ДРУГИМ(!) значением параметра и из полученных чисел формирует собственное возвращаемое значение.
Т.е. справа - результат вызова других экземпляров функции, а слева - значение, которое она вернет наружу.

Кстати, обрати внимание, если при рекурсивном вызове значение параметра не изменяется, то рекурсия не когда не может закончиться. Т.е. ВСЕГДА нужно проверять, чтобы
1. Передаваемое п рекурсии значение не совпадало с входным
2. Существовало корректное условие завершения рекурсии.

Вроде.
Путь(n) = Путь(n-2) + 2 в /
например Путь(5)= Путь(3)+ 2 в степени 2..
степень увеличивается на 1..

или вот еще один бред:
Путь(7)= Путь(5) +(Путь(5) -Путь(3))*2

Уже ближе к истине, но всё равно - как в итоге выглядит общая формула
f(n) = ?

судя по тому, что было выше, то: *ну да
f (n):= f(n-2)+ (f(n-4)-f(n-2))*2

больше пока идей нету..

Что здесь такое f-2? Перечитай хотя бы то, что написала.

я имела в виду:
f (n):= f(n-2)+ (f(n-2)-f(n-4))*2
но оно все равно неверно

Давай пойдем другим путем, ты перестанешь гадать, и начнешь рассуждать, договорились? Начнем с самого простого варианта твоего "дерева": допустим, что оно выглядит так:

  1  
2 3 4

(разные значения узлов - просто чтоб проще ориентироваться). Представила себе это? Допустим (я говорю, допустим, пока), тебе уже известно, сколько путей пожара есть от вершины "2", от вершины "3" и от вершины "4".

А теперь добавляем еще один уровень, внизу:

    1    
  2 3 4  
5 6 7 8 9

Как теперь, зная, сколько путей есть из "2" и из "3", найти, сколько путей есть из "5" или из "6"?

Договорились.
Насколько мой воспаленный мозг соображает:
То есть из "5" будет столько же путей сколько и из "2" , ;
из "6" будет столько путей сколько из "3" +из "2"


Добавлено через 9 мин.
из середины и из вершин только один путь.

А я не говорил ,что тебе известно число путей из "5", заметь... Кроме того, вершины "5" и "7" никак не связаны между собой, поэтому и при вычислении f("7") - обозначим это так - ты не должна рассматривать f("5"). Семерка связана ТОЛЬКО с "3", поэтому придется тебе выражать количество путей из "7" через количество путей из "3"...

Неправда... Из "6" ты можешь пойти либо через "2" (тогда число путей будет равно тому, что нам известно для "2"), либо через "3" (тогда число путей совпадет с их числом для "3"). А всего их будет f("6") = f("2") + f("3")

Возражения?

Да, это я поняла.

если честно, не смогла применить эту логику...
поэтому просто подогнала формулу..

В данном случае мне кажется более продуктивным №обратить" задачу. Т.е. двигаться по дереву не от основания к вершине (в направлении распространения пламени), а от вершины к основанию (т.е. в обратном направлении).
Очевидно, в каждой вершине образуются два новых пути кроме центрального ствола, где их три.

Ну, и что у тебя получилось? Какова окончательная "подогнанная" формула?

f(n)=f(n-1)*2+1

И как же тогда будет выглядеть код функции на паскале?

Это неправильная формула. По крайней мере ты не вычислишь по ней ничего. Чему, скажем, равно F(1)?

тогда я вообще не понимаю/

Тебе уже неоднократно говорили, что надо ставить граничные условия. Если б ты написала, что
f(n) = f(n-1) * 2 + 1; f(0) = 0 - это уже можно было бы запрограммировать. А так у тебя нет ни малейшего шанса дождаться вычисления по приведенной тобой формуле: программа все время будет искать предыдущее значение. До бесконечности. Практически же все окончится гораздо раньше: как только переполнится стек - программа вылетит с ошибкой.

Вот, например, формула, которая выдаст правильный ответ (если правильно запрограммировать функцию, и правильно ее вызвать):
f(0) = 0; f(1) = 1; f(n) = f(n - 1) + 2(f(n - 2) + 1)

а если я сделаю так:

FUNCTION f(n : longint) : Longint;
BEGIN
IF n = 1 THEN f := 1
   ELSE f := f(n-2)*2+1
END;

?

Добавлено через 3 мин.
вычисляет верно..

> вычисляет верно..

Ну и хорошо.

Добавлено через 2 мин.
От себя добавлю: я даже не буду придираться к *2 вместо shl 1, всё равно пытаться оптимизировать вычисление степени двойки через рекурсию бесполезно, а если уж оптимизировать, то ответ писать в виде f := 1 shl (n shr 1 + 1) - 1, но он, увы не соответствую требованию задания непременно воткнуть рекурсию.

но все равно ведь формула должна быть другая..

Формула правильная, в чём проблема?

не знаю. просто я очень долго мучалась. пыталась найти какие-то решения. а тут раз и ..

всем большое спаcибо.

Volvo,спасибо) оказывается эта логика очень даже пригодилась.
нужно было сделать функцию с 2 параметрами: номер уровня и номер буквы по счету.