Рекурсия в Паскале, помогите разобраться

[Василий_0110]

Функция F(n) для целых неотрицательных чисел n определяется следующим образом: F(0)=0, F(1)=1, F(2n)=F(n), F(2n+1)=F(n)+F(n+1). Для заданного n нужно найти и напечатать F(n). Обязательное условие: n столь велико, что недопустимо организовывать массив из n чисел. Это ведь рекурсия? 2n - это четные числа, а 2n+1 - нечетные, я так понимаю? А если попытаться вручную вычислить значение ф-ии при n=2 и большем значении, то значение ф-ии чему будет равно-то, я не могу понять ?

[eoln]

Сообщение от Василий_0110

n столь велико, что недопустимо организовывать массив из n чисел. Это ведь рекурсия?

Нет, если для массива это много, то для рекурсии это ОЧЕНЬ много.
Это рекуррентность

Значения следующие
F(0)=0
F(1)=1
n=1
F(2)=F(1)=1
F(3)=F(1)+F(2)=2
n=2 аналогично
F(4)=1
F(5)=3
n=3
F(6)=2
F(7)=3
n=4
F(8)=1
F(9)=4
Предложу идею. Например при n=214 для вычисления F(214) нужно знать 107 - ое значение, для 107 нужно знать 53 и 54, для них нужно знать 27+26 и 27, и т.д Таблица примерно такая:
214
107 -
53 54
26 27
13 14
6 7
3 4
1 2
То есть массив на 214 элементов тут не нужен вовсе, достаточно массива на 14 элементов. Т.е. нужен массив MAS[1..X, 1..2]. Чтобы узнать чему равен Х, можно посмотреть на 1-ый столбей таблицы - он получен путём целочисленного деления предыдущего значения на 2 (т.е., если не ошибаюсь, то не более логарифма по основанию 2 от n).
И по памяти должно проходить даже при запредельных n. Поэтому чтобы не вычислять чтоже за число в массиве по конкретному адресу, можно массив на 4 элемента в строке сделать (там будет хранится не только результат операций, но и сами числа) - это сделает код более быстрым и читабельным, но увеличит память (что вообще не критично учитывая быстрое убывание логарифмической ф-ии справа на лево).
Всё сказанное не проверено и за проблемы, возникающие в процессе эксплуатации, распространитель ответственности не несёт