Todas as funções recursivas podem ser codificadas com iterações? [fechadas]

10

Quais são as vantagens da recursão?

Algumas linguagens de programação podem otimizar a recursão da cauda, ​​mas, ainda em termos gerais, a recursão consome mais recursos do que os loops regulares.

É possível ter uma versão iterativa de alguma função recursiva?

OscarRyz
fonte

Respostas:

10

Sim, você pode codificar funções recursivas como iterações. Basicamente, você precisa manter as informações manualmente, que de outra forma seriam tratadas pelo método que chama o código gerado pelo compilador.

Em outras palavras, você precisa de uma pilha em que cada entrada seja uma estrutura que contenha os parâmetros passados ​​e todas as variáveis ​​locais. Você sempre trabalha na entrada mais alta da pilha. Se precisar ligar para si mesmo, crie uma nova entrada e coloque em cima da pilha. Quando terminar, pegue a entrada mais alta da pilha, expondo a abaixo, e use a entrada mais alta anteriormente para extrair os valores de retorno e atualizar a nova entrada mais alta de acordo.

Sugiro que você estude um livro do compilador para ver como isso geralmente é implementado no código da máquina.


fonte
Entendi. Então, que vantagem teria a recursão? Simplicidade?
OscarRyz
2
@OscarRyz: Sim, e é mais elegante.
Michael K
@OscarRyz, da maneira que descrevi é recursão. Isso simplesmente não é feito com instruções nativas da CPU. Fazer isso manualmente permite que você faça coisas - como paralelização - que mapeiam mal as instruções nativas.
15

A recursão geralmente é uma maneira mais natural de ver as coisas do que a iteração. Por exemplo, considere a passagem inorder de uma árvore binária: inorder(left); process(); inorder(right);é muito mais simples do que manter explicitamente uma pilha.

Enquanto você não for muito fundo (explodindo a pilha), a diferença no uso de recursos é geralmente trivial. Não se preocupe com isso em geral. O código simples é normalmente melhor que o código otimizado à mão, embora haja exceções. Certo é normalmente melhor que rápido.

Qualquer algoritmo recursivo pode ser expresso como um algoritmo iterativo, mas pode ser necessário manter uma pilha explícita (correspondente à pilha de chamadas manipulada implicitamente). Afinal, se você compilar uma função recursiva, obtém algo que depende da manipulação de uma pilha e do loop da função, e isso é iterativo.

Funções recursivas de cauda podem ser facilmente traduzidas em loops e não precisam de uma pilha, mas esse é um caso especial.

David Thornley
fonte
8
Eu diria que certo é sempre melhor que rápido. Código que faz a coisa errada muito rapidamente não é muito bom para ninguém.
Mason Wheeler
11
Mas e se você puder fazer a coisa errada muito rápido ?!
RationalGeek
11
@jkohlhepp - Posso resolver qualquer problema instantaneamente. A resposta é 0.
Note-se: pense em um nome
2
Usar recursão em vez de uma pilha explícita pode ser mais eficiente - evitando a necessidade de alocações de heap, possível fragmentação de memória e possíveis problemas de localidade. No entanto, "à direita é normalmente melhor que rápido", o excesso de pilha nos casos em que seu software precisa lidar significa que seu código está quebrado. Geralmente, os casos de problemas são bastante fáceis de detectar - a recursão em uma árvore (razoavelmente) equilibrada é boa, mas a recursão em uma árvore que pode estar muito desequilibrada ou em uma lista vinculada pode ser um bug sério em um idioma como C. Pior , ele pode sobreviver a testes simples e apenas travar quando implantado de verdade.
precisa saber é o seguinte
11
Eu acho que todos vocês entendem o que Mason quis dizer e estão apenas fazendo piadas por diversão. Obviamente, um programa lento e correto é mais útil do que um programa rápido e incorreto.
Giorgio
4

Quais são as vantagens da recursão?

Tente resolver o problema das Torres de Hanói de forma iterativa. Depois de desistir, dê uma olhada na solução iterativa e compare com a solução recursiva. Qual é o mais simples?

É possível ter uma versão iterativa de alguma função recursiva?

Sim, em princípio. No entanto, para muitos problemas, incluindo tarefas muito comuns, como travessias de árvores, as soluções recursivas são muito mais simples e mais elegantes que as iterativas.

Dima
fonte
3

Quais são as vantagens da recursão?

Simplicidade. Sem a otimização de chamada final, é claro que é preciso mais recursos (pilha), mas como você implementaria, digamos, deltreeem Java sem recursão? O problema é que delete()só é possível excluir diretórios se estiverem vazios; aqui está com recursão:

deltree(File fileOrDirectory) {
    if (fileOrDirectory.isDirectory()) {
        for (File subFileOrDirectory : fileOrDirectory.listFiles()) {
            deltree(subFileOrDirectory);
        }
    }
    fileOrDirectory.delete();
}
Joonas Pulakka
fonte
11
Com uma pilha, conforme mencionado por outras respostas.
Nicole
Sim, mas quão simples é isso?)
Joonas Pulakka
Oh, a recursão é definitivamente melhor. Eu pensei que você estava dizendo que não era possível.
Nicole
0

Acredito que a recursão é uma daquelas ferramentas que um programador deve ter para viver. Com a recursão, você pode "pensar" em seus algoritmos e resolvê-los da maneira que você pensou sobre isso. Mas, devo adverti-lo, todo mundo está falando sobre o quão bonita é a recursão e quanta simplicidade traz ao código, pois tenho algumas coisas a dizer:

  1. Antes de tudo, pensar na "maneira recursiva" de um algoritmo não é fácil. Construir uma função como um fatorial (n!) Ou algo como Hanoi Towers é apenas a ponta do iceberg, e chegar ao fundo requer um tempo muito longo.
  2. Não pense que a recursão traz simplicidade apenas ao seu código; às vezes, a maneira iterativa é feia e confusa, mas é rentável (veja a solução recursiva do problema de Fibonacci)

Tendo essas coisas em mente, aprenda a recursão! é engraçado, complexo e esmagará seu cérebro !, mas você se sentirá adorando.

Boa sorte!

David Conde
fonte