Может ли каждая рекурсия быть преобразована в итерацию? - PullRequest
Новая
       72

Может ли каждая рекурсия быть преобразована в итерацию?

174 голосов
/ 31 мая 2009

A reddit thread поднял интересный вопрос:

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

Примером (счетчика?) В сообщении является пара: 

(define (num-ways x y)
  (case ((= x 0) 1)
        ((= y 0) 1)
        (num-ways2 x y) ))

(define (num-ways2 x y)
  (+ (num-ways (- x 1) y)
     (num-ways x (- y 1))

Ответы [ 18 ]

0 голосов
/ 06 мая 2010

tazzego, рекурсия означает, что функция будет вызывать сама себя, нравится вам это или нет. Когда люди говорят о том, можно или нет что-либо сделать без рекурсии, они имеют в виду это, и вы не можете сказать «нет, это неправда, потому что я не согласен с определением рекурсии» как действительное утверждение.

Имея это в виду, почти все остальное, что вы говорите, - чепуха. Единственное, что вы говорите, не является чепухой, это идея, что вы не можете представить программирование без стека вызовов. Это то, что делалось десятилетиями, пока использование стека вызовов не стало популярным. В старых версиях FORTRAN не было стека вызовов, и они работали просто отлично.

Между прочим, существуют языки, полные по Тьюрингу, которые реализуют только рекурсию (например, SML) в качестве средства зацикливания. Существуют также языки, полные по Тьюрингу, которые реализуют итерацию только как средство зацикливания (например, FORTRAN IV). Тезис Черча-Тьюринга доказывает, что все, что возможно на рекурсивных языках, может быть сделано на нерекурсивном языке, и наоборот, благодаря тому, что оба они обладают свойством полноты по Тьюрингу.

0 голосов
/ 06 мая 2010

Вопрос: если в первую очередь функция делает свою копию в случайном пустом пространстве памяти, а затем вместо того, чтобы вызывать саму себя, вызывает копию, является ли это все еще рекурсией? (1) Я бы сказал, да.

Является ли явное использование стека реальным способом удаления рекурсии? (2) я бы сказал нет. По сути, разве мы не подражаем тому, что происходит, когда мы используем явную рекурсию? Я считаю, что мы не можем определить рекурсию просто как «функцию, которая сама вызывает», так как я вижу рекурсию также в «коде копирования» (1) и в «явном использовании стека» (2).

Более того, я не вижу, как КТ демонстрирует, что все рекурсивные алгоритмы могут стать итеративными. Мне только кажется, что «все», обладающее «мощью» машины Тьюринга, может выражать все алгоритмы, которые это может выразить. Если машина Тьюринга не может рекурсия, мы уверены, что у каждого рекурсивного алгоритма есть свой интерактивный перевод ... Машина Тьюринга может рекурсию? По моему мнению, если это можно «реализовать» (любым способом), то можно сказать, что оно есть. Есть это? Я не знаю.

Все настоящие процессоры, которые я знаю, могут рекурсии. Честно говоря, я не понимаю, как программировать по-настоящему, не имея стека вызовов, и я думаю, что именно это делает рекурсию возможной в первую очередь.

Избегая копирования (1) и «имитированного стека» (2), мы продемонстрировали, что каждый рекурсивный алгоритм может быть на реальных машинах выражен итеративно ?! Я не вижу, где мы это продемонстрировали.

0 голосов
/ 02 ноября 2009

Посмотрите на следующие записи в википедии, вы можете использовать их в качестве отправной точки, чтобы найти полный ответ на ваш вопрос.

Следует параграфу, который может дать вам подсказку, с чего начать:

Решение рекуррентного отношения означает получение решения в замкнутой форме : нерекурсивная функция n.

Также взгляните на последний абзац этой записи .

0 голосов
/ 31 мая 2009

Вот итерационный алгоритм: 

def howmany(x,y)
  a = {}
  for n in (0..x+y)
    for m in (0..n)
      a[[m,n-m]] = if m==0 or n-m==0 then 1 else a[[m-1,n-m]] + a[[m,n-m-1]] end
    end
  end
  return a[[x,y]]
end
0 голосов
/ 31 мая 2009

Appart из явного стека, другой шаблон для преобразования рекурсии в итерацию с использованием батута.

Здесь функции либо возвращают конечный результат, либо закрывают вызов функции, который он в противном случае выполнил бы. Затем инициирующая (трамплинная) функция продолжает вызывать возвращаемые замыкания, пока не будет достигнут конечный результат.

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

http://en.wikipedia.org/wiki/Trampoline_(computers)

0 голосов
/ 31 мая 2009

Удаление рекурсии является сложной проблемой и выполнимо при четко определенных обстоятельствах.

Ниже приведены простые случаи:

0 голосов
/ 25 января 2016

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

Подробнее: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Functions

0 голосов
/ 02 ноября 2009

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

Страница:
...