Количество свечей, которые можно поставить(повесить) на Рождественскую елку зависит от высоты(h) елки.
Изучите следующие примеры освещения свечами:


1 рис. h = 1. Candles = 1;
2 рис. h = 2. Candles = 4;
3 рис. h = 3. Candles = 13;
a)Укажите(дайте) рекурсивное определение и рекурсивный алгоритм для Candles(h).
b) Реализуйте итеративный ввод с действием для Candles(h).

Честно говоря, вообще не понимаю как это делать..
Объясните, пожалуйта, если кто понял, что нужно вообще делать в этом задании.
Не понимаю как это можно делать с помощью рекурсии..да и вообще не понимаю как это делать.

Подозрительно похоже на Салфетку Серпинского. Посмотри в FAQ-е, klem4 по-моему, показывал, как такое делается...

Спасибо, volvo. Просто не было понятно , что это вообще.
Попробую разобраться.

Как выяснилось (хотя возможно и неверно), что количество
Candles =(3 в степени (h-1)) + (3 в степени (h-2))

Вроде сходится..
а как применить на практике не знаю
саму рекурсию не особо понимаю.
Не мог бы кто-нибудь объяснить как это можно сделать.

всё...терь я совсем запуталась.

Ну если я правильно понимаю поставленную задачу, то при h = 4 ответ будет 40, и при этом соотношени Candles(h) = 3^(h-1) + 3^(h-2) неверно...

Но тогда верно другое соотношение, а именно : Candles(h) = 3 * Candles(h - 1) + 1; Candles(1) = 1.

Программно это реализуется так :



При этом функция Candles вызывает сама себя до тех пор, пока h не станет равным 1. После этого рекурсия как бы возвращается назад, используя полученные значения... Вообще конечно это сложно объяснить .

Не сходится, потому что неверно. Верная формула: Candles(h) = (3^h - 1) / 2

Спасибо,Tony . Но я все равно не могу понять как работают эти рекурсии.

Добавлено через 2 мин.
volvo , а как ты откопал эту формулу?.

А чего ее откапывать? Я ее и не закапывал вообще-то. У меня память хорошая, если честно, я просто помню много разных формул...

Вообще-то формулы не откапываются, а выводятся.

я это и имела в виду.

Спасибо . Теперь, кажется, начинаю понимать как работают рекурсии.
Вот такая вот функция получилась с итерацией:

FUNCTION CandlesIter (h : Integer):integer;
VAR i, c : integer;
    temp :integer;
BEGIN
temp:=0;
        FOR i:= 1 TO h DO
                 temp:= 3*temp+1;
                 CandlesIter:=temp;
END;

А где тут рекурсия?

Как видишь, тут рекурсии нет.
Я говорю о той функции, которую написал Tony.