избавиться от рекурсии, переписать функцию Опции

[compiler]

Добрый день!
Есть следующие функция:

function f_a(const n : integer): longint;
begin
   if n <= 1 then f_a:=1 else
      f_a:=n - f_a(f_a(n-1));
end; { f_a }

Необходимо переписать функцию, избавившись от рекурсии.

Для n>=0 получаем:

Код

  1   1   2   3   3   4   4   5   6   6   7   8   8   9   9  10  11  11  12  12  13  14  14  15  16  16  17  17  18  19  19  20  21  21  22  22  23  24  24  25...

То есть мы имеем цифры идущие парами, но через 3 или 5 хода встречается "цифра-одиночка".

Что с этим делать - не знаю. Буду рад помощи.

Сообщение отредактировано: compiler - 15.05.2008 15:47

[volvo]

Последовательность Хольфштадтера?

function myFa(n: integer): longint;
  function sigma: real;
  begin
    sigma := (sqrt(5)-1) / 2;
  end;
begin
  myFa := trunc(sigma*(n + 1));
end;

, если не ошибаюсь...

[Michael_Rybak]

в теле функции заводи массив значений (можно выделять динамически), и последовательно заполняй его циклом for слева направо.

[compiler]

Последовательность Хольфштадтера?

И откуда ты это знаешь?

в теле функции заводи массив значений (можно выделять динамически), и последовательно заполняй его циклом for слева направо.

То есть, вместо рекурсивного вызова функции мы получаем рекурсивное обращение к элементам массива.. Где-то я такое уже видел, да подзабыл уже...

Спасибо!

[Michael_Rybak]

получаем рекурсивное обращение к элементам массива

да, вроде того

есть еще рекурсия с запоминанием промежуточных результатов.

это когда к итерации не переходишь (не заменяешь рекурсию циклом), но заводишь внешний массив, и в рекурсивной процедуре всегда сохраняешь полученный результат в этот внешний массив.

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

[compiler]

есть еще рекурсия с запоминанием промежуточных результатов. ...

интересно, интересно... надо будет попробовать написать так несколько функций..
ещё раз спасибо.

[hardcase]

интересно, интересно... надо будет попробовать написать так несколько функций..
ещё раз спасибо.

Это еще называется динамическим программированием.

[compiler]

Это еще называется динамическим программированием.

буду знать, спасибо..