Итеративные и рекурсивные функции

[Alhimik]

Всем привет! Тут что-то на философию потянуло. Правда ли, что для каждой рекурсивной функции существует итеративная функция? На Википедии (http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D1%8F)
пишут, что

Цитата:

Теоретически, любую рекурсивную функцию можно заменить циклом и стеком.

С другой стороны, на сайте http://proger.org.ua/index.php/algoritmy/28-ponyatie-iteratsii-i-rekursii-iterativnye-i-rekursivnye-vychisleniya утверждается обратное:

Цитата:

Рекурсия не всегда может быть заменена итерацией.

Где истина?

[Joker_vD]

В первом случае.

[Alhimik]

Ага! Я так и думал, что на Википедии надёжнее. Однако, хотелось бы получить обоснование (или ссылки на более фундаментальные работы по программированию или математике). Такой вот я недоверчивый.

[Pavia]

Alhimik
Истина по середине. Компьютерная наука это естественная наука хотя математики и постарались её описать строго но проблема в корне, а именно в определениях. Понятия алгоритм, функция, интерация - довольно расплывчато.

Интерация это повтор алгоритма.
Рекурсия это вызова функций самой себя.
Т.е. тоже повтор алгоритма только самого себя. Собственно доказательство окончено.

Что касается стека. Он нужен для запоминания состояния функции для возврата из рекурсии.

Есть класс рекурсивных функций которые могут быть представлены без использования стека.

Более строгое доказательство надо читать в книгах по теории вычисления. Но суть не измениться.

[nikvic]

Pavia в сообщении #780665 писал(а):

Понятия алгоритм, функция, интерация - довольно расплывчато.

Понятие алгоритма столь же аккуратно, что и действительного числа - с его тремя вариантами.

[alex7851]

Alhimik в сообщении #780573 писал(а):

Правда ли, что для каждой рекурсивной функции существует итеративная функция?

Например, для функции Аккермана нет. Есть стек, который предоставляется ОС при запуске программы, можно вручную использовать свой стек (например, когда не хватает объема), но суть от этого не поменяется.

(Оффтоп)

Какая, кстати, у функции Аккермана выч. сложность?

[iifat]

alex7851 в сообщении #780727 писал(а):

Например, для функции Аккермана нет

Ересь глаголете. Есть. Поищу у себя.
Нашёл. Это, правда, tcl, но, надеюсь, идея понятна.

proc accrec {m n} {
  puts "$m $n"
  if {!$m} {
    expr {$n+1}
  } elseif {!$n} {
    accrec [expr {$m-1}] 1
  } else {
    accrec [expr {$m-1}] [accrec $m [expr {$n-1}]]
  }
}
 
puts [accrec 3 3]
 
proc accloop {m n} {
  set state 1
  set stack {}
  set acc 0
  set mm $m; set nn $n
  while {1} {
    puts ":: $state $mm $nn"
    set action 0
    switch $state {
      {1} {
    if {!$mm} {set acc [expr {$nn+1}]; set action -1} else {set state 2}
      }
      {2} {
    if {!$nn} {set newmm [expr {$mm-1}]; set newnn 1; set action 1; set state 3} else {set state 4}
      }
      {3} {
    set action -1
      }
      {4} {
    set newmm $mm; set newnn [expr {$nn-1}]; set action 1; set state 5
      }
      {5} {
    set newmm [expr {$mm-1}]; set newnn $acc; set action 1; set state 6
      }
      {6} {
    set action -1
      }
    }
    if {$action==-1} { # возврат
      if {![llength $stack]} break
      set stack [lassign $stack mm nn state]
      puts "<== ($mm $nn $state) $stack -- $acc"
    }
    if {$action==1} { # рекурсия
      set stack [linsert $stack 0 $mm $nn $state]
      puts "==> $stack"
      set state 1; set mm $newmm; set nn $newnn
    }
  }
  return $acc
}
 
puts [accloop 3 3]

[alex7851]

iifat в сообщении #780734 писал(а):

Это, правда, tcl, но, надеюсь, идея понятна.

Похоже на автомат.

[iifat]

А то ж

[_Ivana]

По кустарному: допустим, у нас есть функция, использующая рекурсию. Мы посчитали, что в самом максимальном случае при ее выполнении глубина рекурсии (количество вложенных вызовов) составит $N$. Теперь мы пишем в тексте кода $N$ копий этой функции, и при каждом вложенном вызове вызываем очередную копию. Рекурсия ли это? Зависит от определения, но стек загружается точно так же, не считая не оптимального кода. А если ставить вопрос не о рекурсии, а о минимизации используемой ОЗУ, тогда становится интереснее. Даже если мы откажемся от использования функции как таковых, чтобы не помещать каждый раз в стек (системный или собственный) весь контекст и адрес возврата, то нам все равно может понадобиться память для хранения результата истории вызовов. Например, функцию $cos(cos(cos(cos(......cos(27)))))$ можно написать рекурсивно, со всеми прелестями загрузки стека, или просто в цикле "с конца" при единственном уровне вложенности функций. А функцию обхода графа из вершины мы можем написать как угодно, но сам путь при этом нам придется все равно хранить, хотя и в этом случае вложенные контексты в стеке не обязательны.

[Joker_vD]

_Ivana в сообщении #780881 писал(а):

Мы посчитали, что в самом максимальном случае при ее выполнении глубина рекурсии (количество вложенных вызовов) составит $N$.

int diverge(int x) = { return diverge (x); } — с любым x ее запустите, и количество вложенных вызовов превысит любое натуральное $N$. Но это не мешает переписать ее как int diverge(int x) = { while(true); return 0; }.

[Alhimik]

Короче, Википедия рулит. И таки для любой рекурсивной функции существует итеративная.

[iifat]

_Ivana в сообщении #780881 писал(а):

вопрос не о рекурсии, а о минимизации используемой ОЗУ

Вопрос не о рекурсии и не о минимизации, имхо. То бишь, изначально, когда первые языки высокого уровня её не допускали, он стоял о рекурсии. Сейчас, имхо, он стоит о том, что принято память под стек выделять в начале программы и не увеличивать. Так что сейчас единственный смысл — использование динамической памяти вместо стековой. Ну, ещё, конечно, экономия, но не думаю, что это главный мотив.

[_Ivana]

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

iifat Не вижу противоречий. Вопрос не в рекурсии, а в хранении всех контекстов глубины вызовов или не хранении (неважно где, в стеке или еще где). Память все равно конечна, да даже если разбрасываться ею, то быстродействия все эти сохранения/восстановления контекстов не прибавляют. Зато рекурсия очень изящно выглядит в тексте программы на языке высокого уровня - пара строк функции, лаконично и красиво. А компилятор сам займется контекстом по его колл-конвеншионз, сделает все что надо. Так что тут как всегда выбор, со всеми плюсами и минусами каждого варианта.
ЗЫ и программы пишут не только для компов, где есть ОС и вагон памяти, так что мотивы экономии в условиях ограниченных ресурсов встают на первое место.

[Joker_vD]

_Ivana в сообщении #781136 писал(а):

бесконечные рекурсии не применяются хотя бы потому, что быстро заполнят весь стек адресами возврата

Если компилятор настаивает на реализации рекурсивного поведения исключительно с помощью CALL — это его проблемы.

К тому "мэйн луп" — это, строго говоря, пример корекурсии, а она бесконечна по сути своей.