Как убрать переполнение программного стека?

Question

[kan3k1k3n]

у меня есть рекурсивная функция для вычисления следующего члена последовательности:
a1 = −2, a2 = 2, an = 3an−1 − an−2
код:

function f(n: integer): integer;
begin
  if n = -2
  then f:= 1
  else if n = 2
  then f:= 2
  else f:= 3*f(n-1)-f(n-2);
end;
var n: integer;
begin
  write('n = ');
  readln(n);
  write(f(n))
end.

если я ввожу n = 3, то выдается ошибка: Программа завершена из-за переполнения программного стека.
как это решить?

Comments

[Hemul GM]

Скорректировать условие

[kan3k1k3n]

Hemul GM, а как именно. что не так в моем условии?

[kalapanga]

kan3k1k3n, у Вас написано: если n=-2 тогда f:=1. А надо-то наоборот: если n=1 тогда f:=-2.

[alexalexes]

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

function f(n: integer, current_level: integer): integer;
begin
 if current_level > 1000 "В начале рекурсивной функции сразу проверяем, не вышли мы за какое-то отладочное значение, например, 1000"
   write('Что-то пошло не так, достигнут предел рекурсии!')
 else
...
else f:= 3*f(n-1, current_level + 1)-f(n-2, current_level + 1); "Добавляем и прибавляем значение уровня при рекурсивном вызове"
...
write(f(n, 1)) "Уровню рекурсии задаем начальное значение"

Answer 1

[Alexandroppolus]

Не помню паскалевского синтаксиса, но как-то так:

function f(n: integer): integer;
var a, b, c: integer;
begin
  if n < 2
  then f:= -2
  else if n = 2
  then f:= 2
  else
  begin
     a := -2;
     b := 2;
     for i = 3...n begin
        c := b;
        b := 3*b - a;
        a := c;
     end;
     f:= b;
   end;
end;

Как видим, рекурсия тут без надобности

Comments

[Hemul GM]

Поправил

function f(n: integer): integer;
var 
  a, c: integer;
begin
  if n < 2 then Exit(-2);
  if n = 2 then Exit(2);

  var a := -2;
  var Result := 2;
  for var i := 3 to n do
  begin
     c := Result;
     Result := 3 * Result - a;
     a := c;
  end;
end;

Answer 2

[Mutilator]

Первое условие остановки не соответствует формулировке задания.
У тебя:

if n = -2
  then f:= 1

...а согласно формуле

a1 = −2, a2 = 2, aN = 3aN−1 − aN−2

должно быть:

if n = 1
  then f:= -2