2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 "Наивный" подход к рекурсии
Сообщение18.12.2021, 10:56 
Делал задание на Питоне: генерация QHofstadter.
${\displaystyle {\begin{aligned}
Q(1)=Q(2)=1,
\\Q(n)=Q(n-Q(n-1))+Q(n-Q(n-2)),\quad n>2
\end{aligned}}}
$
Использовал мемоизацию, т.е. запоминались уже использованные значения.
Это навело меня на такой вопрос.
В чем собственно "проблема" с другими начальными значениями, отличными от (1,1)?
В том, что в процессе рекурсии возникают не определенные ранее значения.
Ну так давайте определим их!
В Питоне это просто. При обращении к словарю по несуществующему ключу вместо выдачи ошибки этому ключу присваиваем default значение, например 1.
Получилась интересная картина. Если $Q(1)=Q(2)=2$, то достаточно определить $Q(0)=1$ и далее рекурсия продолжается без помех.
(Это конечно численный результат, ведь даже для классической QHofstadter неизвестно, определена ли она всюду)

При других начальных значениях запрос на дополнительные опускается глубже в отрицательные числа,
иногда опять "выныривает", но чаще уходит все дальше.
Вот результат наблюдений. Делалось 100 рекурсий для $1 < Q(1), Q(2) < 20$
В таблице приведена максимальная глубина запроса на неопределенные значения.
Красным выделено то, что явно неограниченно, зеленым - то, где после добавления новых начальных данных рекурсия продолжается.
Изображение
Видно, что при $1 < Q(1) < 10$ ситуация нетривиальная.

Разумеется, подобный подход можно применить к любой рекурсивной функции.
Мне интересно, делалось ли ранее подобное, какие есть результаты?

 
 
 
 Re: "Наивный" подход к рекурсии
Сообщение15.04.2022, 06:42 
Аватара пользователя
"Отлаженная программа - это такая, которая выдаёт какой-то результат".
Ваше предложение эквивалентно тому, чтобы добавить в начальные условия $Q_i=1, i \le 0$
Что не то, чтобы заведомая ошибка, но произвол. Ответ становится зависимым от волевого решения - что считать дефолтным значением. То, что программа всегда что-то да выдаёт - прекрасно, но бесполезно.

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group