Todos os algoritmos iterativos podem ser expressos recursivamente?

StackOverflow https://stackoverflow.com/questions/2093618

Pergunta

Caso contrário, existe um bom exemplo de contador que mostre um algoritmo iterativo para o qual não existe contraparte recursiva?

Se for verdade que todos os algoritmos iterativos podem ser expressos recursivamente, há casos em que isso é mais difícil de fazer?

Além disso, qual o papel da linguagem de programação em tudo isso?Posso imaginar que os programadores de Scheme têm uma abordagem diferente sobre iteração (= recursão final) e uso de pilha do que os programadores somente Java.

Foi útil?

Solução

Há uma prova ad hoc simples para isso. Como você pode construir uma linguagem completa de Turing usando estruturas estritamente iterativas e uma linguagem completa, usando apenas estruturas recursivas, os dois são, portanto, equivalentes.

Outras dicas

Todos os algoritmos iterativos podem ser expressos recursivamente?

Sim, mas a prova não é interessante:

  1. Transforme o programa com todo o seu fluxo de controle em um único loop contendo uma única instrução case em que cada ramificação é um fluxo de controle linear, possivelmente incluindo break, return, exit, raise, e assim por diante.Introduza uma nova variável (chame-a de "contador de programa") que a instrução case usa para decidir qual bloco será executado em seguida.

    Esta construção foi descoberta durante as grandes “guerras de programação estruturada” da década de 1960, quando as pessoas discutiam o poder expressivo relativo de várias construções de fluxo de controle.

  2. Substitua o loop por uma função recursiva e substitua cada variável local mutável por um parâmetro para essa função.Voilà!Iteração substituída por recursão.

Este procedimento equivale a escrever um intérprete para a função original.Como você pode imaginar, isso resulta em código ilegível e não é algo interessante de se fazer. No entanto, algumas das técnicas podem ser úteis para uma pessoa com experiência em programação imperativa que está aprendendo a programar em uma linguagem funcional pela primeira vez.

Como você disse, toda abordagem iterativa pode ser transformada em uma abordagem "recursiva" e, com chamadas finais, a pilha também não explodirá.:-) Na verdade, é assim que o Scheme implementa todas as formas comuns de loop.Exemplo no esquema:

(define (fib n)
  (do ((x 0 y)
       (y 1 (+ x y))
       (i 1 (+ i 1)))
      ((> i n) x)))

Aqui, embora a função pareça iterativa, ela na verdade é recorrente em um lambda interno que usa três parâmetros, x, y, e i, e chamando a si mesmo com novos valores a cada iteração.

Aqui está uma maneira pela qual a função pode ser expandida macro:

(define (fib n)
  (letrec ((inner (lambda (x y i)
                    (if (> i n) x
                        (inner y (+ x y) (+ i 1))))))
    (inner 0 1 1)))

Dessa forma, a natureza recursiva torna-se mais aparente visualmente.

Definindo iterativo como:

function q(vars):
  while X:
    do Y

Pode ser traduzido como:

 function q(vars):
    if X:
      do Y
      call q(vars)

Y Na maioria dos casos, incluiria incrementar um contador testado por X. Essa variável deverá ser passada em 'VARs' de alguma forma ao seguir a rota recursiva.

Como observado por pedestal no sua resposta Podemos construir provas mostrando como recursão e a iteração é equivalente e pode ser usada para resolver o mesmo problema; No entanto, mesmo sabendo que os dois são equivalentes, há desvantagens para usar uma sobre a outra.

Em idiomas que não são otimizados para recursão, você pode achar que um algoritmo usando a iteração é mais rápido que o recursivo e da mesma forma, mesmo em idiomas otimizados, você pode achar que um algoritmo usando iteração escrito em um idioma diferente é mais rápido do que o recursivo. Além disso, pode não haver uma maneira óbvia de escrito um determinado algoritmo usando recursão versus iteração e vice -versa. Isso pode levar ao código difícil de ler, o que leva a problemas de manutenção.

Prolog é apenas uma linguagem recursiva e você pode fazer praticamente tudo nele (eu não sugiro que você faça, mas você pode :))

Soluções recursivas são normalmente relativamente ineficiente Quando comparado às soluções iterativas. No entanto, note -se que existem alguns problemas que podem ser resolvidos apenas por meio de recursão e solução iterativa equivalente podem não existir ou extremamente complexos para programar facilmente (exemplo de tal é A função Ackermann não pode ser expresso sem recursão), embora as recursões sejam elegantes, fáceis de escrever e entender.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top