Изменения

Перейти к: навигация, поиск

Теорема о рекурсии

575 байт убрано, 22:09, 14 декабря 2016
→‎Теорема о рекурсии
Приведем конструктивное доказательство теоремы.
Пусть есть вычислимая <tex>V(x,y)</tex>. Будем поэтапно строить функцию <tex>p(y)</tex>. <br> Предположим, что у нас в распоряжении есть функция <tex>\mathrm{getSrc()}</tex>, которая вернет код <tex>p(y)</tex>. Тогда саму <tex>p(y)</tex> можно переписать так:
 <code><font size = "3em"> '''function''' p(y){ V(x,y) { ... }
main() { '''return ''' V(getSrc(), y) } string getSrc() { ... } }</font></code>
Теперь нужно определить функцию <tex>\mathrm{getSrc()}</tex>. Предположим, что внутри <tex>p(y)</tex> мы можем определить функцию <tex>\mathrm{getOtherSrc()}</tex>, состоящую из одного оператора <tex>return</tex>, которая вернет весь предшествующий ей код. Тогда <tex>p(y)</tex> перепишется так.
<code><font size = "3em"> '''function''' p(y){ V(x,y) { ... } main() { '''return''' V(getSrc(), y) }
main() { return V(getSrc(), y) } '''string ''' getSrc() { '''string ''' src = getOtherSrc(); '''return ''' src + "string getOtherSrc() {" + "\n" + "return" + src + "\n" + "}"; } string getOtherSrc() {... } }</font></code> 
Теперь <tex>\mathrm{getOtherSrc()}</tex> определяется очевидным образом, и мы получаем '''итоговую версию''' функции <tex>p(y)</tex>
<code><font size = "3em"> '''function''' p(y){ V(x,y) { ... }
main() { '''return ''' V(getSrc(), y) } string getSrc() { string src = getOtherSrc(); return src + "string getOtherSrc() {" + "\n" + "return" + src + "\n" + "}"; } string getOtherSrc() { return " p(y){ // Возвращаем весь предыдущий код V(x,y) {... }
main() { return V(getSrc(), y) } '''string ''' getSrc() { '''string ''' src = getOtherSrc(); '''return ''' src + "string getOtherSrc() {" + "\n" + "return" + src + "\n" + "}"; }"; } }</font></code> 
}}
Если говорить неформально, теорема о рекурсии утверждает, что внутри программы можно использовать ее код. Это упрощает доказательство некоторых теорем.
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/57834»

Навигация