Запоминаемые рекурсивные функции. Как сделать их безупречными?

Запоминаемые функции - это функции, которые запоминают найденные значения. Посмотрите в центр док-кода, чтобы узнать об этом в Mathematica, если это необходимо.

Предположим, что у вас есть следующее определение

f[0] = f[1] = 1
f[x_] := f[x] = f[x - 1] + f[x - 2]

в одном из ваших пакетов. Пользователь может загрузить пакет и сразу же запросить f [1000]. Это вызовет сообщение об ошибке $RecursionLimit:: reclim и прервется. Даже если пользователь затем пытается что-то меньшее, скажем f [20], к настоящему времени определение f является коррумпированным, и результат не является хорошим. Конечно, разработчик пакета может увеличить лимит рекурсии и предупредить пользователя, но мой вопрос

Как вы можете улучшить определение f, чтобы, если пользователь запрашивает f [1000], он/она получает ответ без каких-либо проблем? Меня интересует способ улавливать вход пользователя, анализировать его и предпринимать любые шаги для оценки f [1000].

Я легко могу представить, что можно изменить предел рекурсии, если входной сигнал больше 255 (а затем вернет его на исходный уровень), но то, что я действительно хотел бы увидеть, - это если есть способ f, чтобы узнать, сколько значений оно "знает" (fknownvalues) и принять любые значения ввода <= fknownvalues ​​+ $RecursionLimit без проблем или увеличить значение $RecursionLimit, если вход выше.

Спасибо за помощь

Ответы

Ответ 1

Вот код, предполагающий, что вы можете определить значение $RecursionLimit из значения входного аргумента:

Clear[f];
Module[{ff},
  ff[0] = ff[1] = 1;
  ff[x_] := ff[x] = ff[x - 1] + ff[x - 2];

  f[x_Integer] :=f[x] =
     Block[{$RecursionLimit = x + 5},
        ff[x]
  ]]

Я использую локальную функцию ff для выполнения основной работы, а f просто вызывает ее завернутую в Block с правильным значением для $RecursionLimit:

In[1552]:= f[1000]
Out[1552]=  7033036771142281582183525487718354977018126983635873274260490508715453711819693357974224
9494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125
598767690091902245245323403501

ИЗМЕНИТЬ

Если вы хотите быть более точным с настройкой $RecursionLimit, вы можете изменить часть вышеприведенного кода как:

f[x_Integer] :=
  f[x] =
    Block[{$RecursionLimit = x - Length[DownValues[ff]] + 10},
    Print["Current $RecursionLimit: ", $RecursionLimit];
    ff[x]]]

Инструкция Print приведена здесь для иллюстрации. Значение 10 довольно произвольно - для получения нижней границы на нем необходимо вычислить необходимую глубину рекурсии и принять во внимание, что количество известных результатов Length[DownValues[ff]] - 2 (так как ff имеет 2 общих определения). Вот несколько способов использования:

In[1567]:= f[500]//Short

During evaluation of In[1567]:= Current $RecursionLimit: 507
Out[1567]//Short= 22559151616193633087251269<<53>>83405015987052796968498626

In[1568]:= f[800]//Short

During evaluation of In[1568]:= Current $RecursionLimit: 308
Out[1568]//Short= 11210238130165701975392213<<116>>44406006693244742562963426

Если вы также хотите ограничить максимальный $RecursionLimit, это также легко сделать, по тем же линиям. Здесь, например, мы ограничим его 10000 (опять же, это будет внутри Module):

f::tooLarge = 
"The parameter value `1` is too large for single recursive step. \
Try building the result incrementally";
f[x_Integer] :=
   With[{reclim = x - Length[DownValues[ff]] + 10},
     (f[x] =
        Block[{$RecursionLimit = reclim },
        Print["Current $RecursionLimit: ", $RecursionLimit];
        ff[x]]) /; reclim < 10000];

f[x_Integer] := "" /; Message[f::tooLarge, x]]

Например:

In[1581]:= f[11000]//Short

During evaluation of In[1581]:= f::tooLarge: The parameter value 11000 is too 
large for single recursive step. Try building the result incrementally
Out[1581]//Short= f[11000]

In[1582]:= 
f[9000];
f[11000]//Short

During evaluation of In[1582]:= Current $RecursionLimit: 9007
During evaluation of In[1582]:= Current $RecursionLimit: 2008
Out[1583]//Short= 5291092912053548874786829<<2248>>91481844337702018068766626

Ответ 2

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

Самоадаптивный предел рекурсии

Clear[f];
$RecursionLimit = 20;
Module[{ff},
 ff[0] = ff[1] = 1;
 ff[x_] := 
  ff[x] = Block[{$RecursionLimit = $RecursionLimit + 2},  ff[x - 1] + ff[x - 2]];
 f[x_Integer] := f[x] = ff[x]]

f[30]
(*
-> 1346269
*)

$RecursionLimit
(*
-> 20
*)

Edit

Попытка установить $RecursionLimit редко:

Clear[f];
$RecursionLimit = 20;
Module[{ff}, ff[0] = ff[1] = 1;
 ff[x_] := ff[x] =
   Block[{$RecursionLimit =
      If[[email protected][] > $RecursionLimit - 5, $RecursionLimit + 5, $RecursionLimit]}, 
       ff[x - 1] + ff[x - 2]];
 f[x_Integer] := f[x] = ff[x]]

Не уверен, насколько он полезен...