O que é recursão e quando devo usá-la?

Question

Um dos tópicos que parece surgir regularmente em listas de discussão e discussões online é o mérito (ou a falta dele) de se formar em Ciência da Computação.Um argumento que parece surgir repetidamente para a parte negativa é que eles vêm codificando há alguns anos e nunca usaram recursão.

Então a questão é:

1. O que é recursão?
2. Quando eu usaria recursão?
3. Por que as pessoas não usam recursão?

Answer 1

Há uma série de boas explicações sobre recursão neste tópico, esta resposta é sobre por que você não deve usá-lo na maioria dos idiomas.* Na maioria das principais implementações de linguagens imperativas (ou seja,todas as principais implementações de C, C++, Basic, Python, Ruby, Java e C#) iteração é muito preferível à recursão.

Para entender o porquê, siga as etapas que as linguagens acima usam para chamar uma função:

1. o espaço é esculpido em a pilha para os argumentos da função e variáveis ​​locais
2. os argumentos da função são copiados para este novo espaço
3. controle salta para a função
4. o código da função é executado
5. o resultado da função é copiado em um valor de retorno
6. a pilha é rebobinada para sua posição anterior
7. o controle volta para onde a função foi chamada

Executar todas essas etapas leva tempo, geralmente um pouco mais do que o necessário para iterar em um loop.No entanto, o verdadeiro problema está na etapa 1.Quando muitos programas são iniciados, eles alocam um único pedaço de memória para sua pilha e, quando ficam sem memória (frequentemente, mas nem sempre devido à recursão), o programa trava devido a um problema. estouro de pilha.

Portanto, nessas linguagens, a recursão é mais lenta e torna você vulnerável a travamentos.Ainda existem alguns argumentos para usá-lo.Em geral, o código escrito recursivamente é mais curto e um pouco mais elegante, desde que você saiba como lê-lo.

Existe uma técnica que os implementadores de linguagem podem usar chamada otimização de chamada final o que pode eliminar algumas classes de estouro de pilha.Dito de forma sucinta:se a expressão de retorno de uma função for simplesmente o resultado de uma chamada de função, então você não precisa adicionar um novo nível à pilha, você pode reutilizar o atual para a função que está sendo chamada.Lamentavelmente, poucas implementações de linguagem imperativas possuem otimização de chamada final integrada.

* Eu adoro recursão. Minha linguagem estática favorita não usa loops, a recursão é a única maneira de fazer algo repetidamente.Só não acho que a recursão geralmente seja uma boa ideia em linguagens que não estão ajustadas para isso.

** A propósito, Mario, o nome típico para sua função ArrangeString é "join", e eu ficaria surpreso se a linguagem de sua escolha ainda não tivesse uma implementação dela.

Answer 2

Exemplo simples de recursão em inglês.

A child couldn't sleep, so her mother told her a story about a little frog,
    who couldn't sleep, so the frog's mother told her a story about a little bear,
         who couldn't sleep, so the bear's mother told her a story about a little weasel... 
            who fell asleep.
         ...and the little bear fell asleep;
    ...and the little frog fell asleep;
...and the child fell asleep.

Answer 3

No sentido mais básico da ciência da computação, a recursão é uma função que chama a si mesma.Digamos que você tenha uma estrutura de lista vinculada:

struct Node {
    Node* next;
};

E se você quiser descobrir o tamanho de uma lista vinculada, pode fazer isso com recursão:

int length(const Node* list) {
    if (!list->next) {
        return 1;
    } else {
        return 1 + length(list->next);
    }
}

(É claro que isso também poderia ser feito com um loop for, mas é útil como uma ilustração do conceito)

Answer 4

Sempre que uma função chama a si mesma, criando um loop, isso é recursão.Como acontece com qualquer coisa, existem bons e maus usos para a recursão.

O exemplo mais simples é a recursão final, onde a última linha da função é uma chamada para si mesma:

int FloorByTen(int num)
{
    if (num % 10 == 0)
        return num;
    else
        return FloorByTen(num-1);
}

No entanto, este é um exemplo fraco e quase inútil porque pode ser facilmente substituído por uma iteração mais eficiente.Afinal, a recursão sofre sobrecarga de chamada de função, que no exemplo acima poderia ser substancial em comparação com a operação dentro da própria função.

Portanto, toda a razão para fazer recursão em vez de iteração deveria ser aproveitar a vantagem pilha de chamadas para fazer algumas coisas inteligentes.Por exemplo, se você chamar uma função várias vezes com parâmetros diferentes dentro do mesmo loop, essa é uma maneira de realizar ramificação.Um exemplo clássico é o Triângulo de Sierpinski.

Você pode desenhar um deles de forma muito simples com recursão, onde a pilha de chamadas se ramifica em 3 direções:

private void BuildVertices(double x, double y, double len)
{
    if (len > 0.002)
    {
        mesh.Positions.Add(new Point3D(x, y + len, -len));
        mesh.Positions.Add(new Point3D(x - len, y - len, -len));
        mesh.Positions.Add(new Point3D(x + len, y - len, -len));
        len *= 0.5;
        BuildVertices(x, y + len, len);
        BuildVertices(x - len, y - len, len);
        BuildVertices(x + len, y - len, len);
    }
}

Se você tentar fazer a mesma coisa com a iteração, acho que descobrirá que é necessário muito mais código para realizar.

Outros casos de uso comuns podem incluir a passagem de hierarquias, por ex.rastreadores de sites, comparações de diretórios, etc.

Conclusão

Em termos práticos, a recursão faz mais sentido sempre que você precisa de ramificação iterativa.

Answer 5

A recursão é um método de resolução de problemas baseado na mentalidade de dividir para conquistar.A ideia básica é pegar o problema original e dividi-lo em instâncias menores (mais facilmente resolvidas), resolver essas instâncias menores (geralmente usando o mesmo algoritmo novamente) e então remontá-las na solução final.

O exemplo canônico é uma rotina para gerar o Fatorial de n.O fatorial de n é calculado multiplicando todos os números entre 1 e n.Uma solução iterativa em C# se parece com isto:

public int Fact(int n)
{
  int fact = 1;

  for( int i = 2; i <= n; i++)
  {
    fact = fact * i;
  }

  return fact;
}

Não há nada de surpreendente na solução iterativa e ela deve fazer sentido para qualquer pessoa familiarizada com C#.

A solução recursiva é encontrada reconhecendo que o enésimo fatorial é n * Fact(n-1).Ou, dito de outra forma, se você souber o que é um número fatorial específico, poderá calcular o próximo.Aqui está a solução recursiva em C#:

public int FactRec(int n)
{
  if( n < 2 )
  {
    return 1;
  }

  return n * FactRec( n - 1 );
}

A primeira parte desta função é conhecida como Caso base (ou às vezes Cláusula de Guarda) e é o que impede o algoritmo de funcionar para sempre.Ele apenas retorna o valor 1 sempre que a função é chamada com valor 1 ou menos.A segunda parte é mais interessante e é conhecida como Etapa recursiva.Aqui chamamos o mesmo método com um parâmetro ligeiramente modificado (decrementamos em 1) e depois multiplicamos o resultado pela nossa cópia de n.

Quando encontrado pela primeira vez, isso pode ser um pouco confuso, por isso é instrutivo examinar como funciona quando executado.Imagine que chamamos FactRec(5).Entramos na rotina, não somos pegos pelo caso base e então ficamos assim:

// In FactRec(5)
return 5 * FactRec( 5 - 1 );

// which is
return 5 * FactRec(4);

Se entrarmos novamente no método com o parâmetro 4, novamente não seremos interrompidos pela cláusula guard e assim terminaremos em:

// In FactRec(4)
return 4 * FactRec(3);

Se substituirmos este valor de retorno pelo valor de retorno acima, obteremos

// In FactRec(5)
return 5 * (4 * FactRec(3));

Isso deve lhe dar uma pista de como a solução final foi alcançada, então aceleraremos e mostraremos cada etapa do caminho:

return 5 * (4 * FactRec(3));
return 5 * (4 * (3 * FactRec(2)));
return 5 * (4 * (3 * (2 * FactRec(1))));
return 5 * (4 * (3 * (2 * (1))));

Essa substituição final acontece quando o caso base é acionado.Neste ponto, temos uma fórmula algébrica simples para resolver, que equivale diretamente à definição de Fatoriais em primeiro lugar.

É instrutivo observar que cada chamada ao método resulta no acionamento de um caso base ou em uma chamada para o mesmo método onde os parâmetros estão mais próximos de um caso base (geralmente chamado de chamada recursiva).Se este não for o caso, o método será executado para sempre.

Answer 6

Recursão é resolver um problema com uma função que chama a si mesma.Um bom exemplo disso é uma função fatorial.Fatorial é um problema matemático onde o fatorial de 5, por exemplo, é 5 * 4 * 3 * 2 * 1.Esta função resolve isso em C# para números inteiros positivos (não testado - pode haver um bug).

public int Factorial(int n)
{
    if (n <= 1)
        return 1;

    return n * Factorial(n - 1);
}

Answer 7

A recursão refere-se a um método que resolve um problema resolvendo uma versão menor do problema e depois usando esse resultado mais algum outro cálculo para formular a resposta ao problema original.Muitas vezes, no processo de resolução da versão menor, o método resolverá uma versão ainda menor do problema, e assim por diante, até atingir um "caso base" cuja solução é trivial.

Por exemplo, para calcular um fatorial para o número X, pode-se representá-lo como X times the factorial of X-1.Assim, o método "recursa" para encontrar o fatorial de X-1, e depois multiplica tudo o que obteve X para dar uma resposta final.Claro, para encontrar o fatorial de X-1, primeiro calculará o fatorial de X-2, e assim por diante.O caso base seria quando X é 0 ou 1, caso em que ele sabe retornar 1 desde 0! = 1! = 1.

Answer 8

Considere um problema antigo e bem conhecido:

Em matemática, o máximo divisor comum (mdc)… de dois ou mais inteiros diferentes de zero, é o maior inteiro positivo que divide os números sem resto.

A definição de mdc é surpreendentemente simples:

onde mod é o operador de módulo (isto é, o resto após a divisão inteira).

Em inglês, esta definição diz que o máximo divisor comum de qualquer número e zero é esse número, e o máximo divisor comum de dois números eu e n é o máximo divisor comum de n e o restante após a divisão eu por n.

Se você quiser saber por que isso funciona, consulte o artigo da Wikipedia sobre o Algoritmo euclidiano.

Vamos calcular mdc(10, 8) como exemplo.Cada etapa é igual à anterior:

1. mdc(10, 8)
2. mdc(10, 10 módulo 8)
3. mdc(8, 2)
4. mdc(8, 8 mod 2)
5. mdc(2, 0)
6. 2

Na primeira etapa, 8 não é igual a zero, então a segunda parte da definição se aplica.10 mod 8 = 2 porque 8 cabe em 10 uma vez com resto 2.No passo 3, a segunda parte se aplica novamente, mas desta vez 8 mod 2 = 0 porque 2 divide 8 sem resto.Na etapa 5, o segundo argumento é 0, então a resposta é 2.

Você notou que o mdc aparece nos lados esquerdo e direito do sinal de igual?Um matemático diria que esta definição é recursiva porque a expressão que você está definindo recorre dentro de sua definição.

Definições recursivas tendem a ser elegantes.Por exemplo, uma definição recursiva para a soma de uma lista é

sum l =
    if empty(l)
        return 0
    else
        return head(l) + sum(tail(l))

onde head é o primeiro elemento de uma lista e tail é o resto da lista.Observe que sum recorre dentro de sua definição no final.

Talvez você prefira o valor máximo em uma lista:

max l =
    if empty(l)
        error
    elsif length(l) = 1
        return head(l)
    else
        tailmax = max(tail(l))
        if head(l) > tailmax
            return head(l)
        else
            return tailmax

Você pode definir a multiplicação de números inteiros não negativos recursivamente para transformá-la em uma série de adições:

a * b =
    if b = 0
        return 0
    else
        return a + (a * (b - 1))

Se aquela parte de transformar a multiplicação em uma série de adições não faz sentido, tente expandir alguns exemplos simples para ver como funciona.

Mesclar classificação tem uma adorável definição recursiva:

sort(l) =
    if empty(l) or length(l) = 1
        return l
    else
        (left,right) = split l
        return merge(sort(left), sort(right))

Definições recursivas estão por aí se você souber o que procurar.Observe como todas essas definições têm casos básicos muito simples, por exemplo., mdc(m, 0) = m.Os casos recursivos reduzem o problema para chegar às respostas fáceis.

Com esse entendimento, agora você pode apreciar os outros algoritmos em Artigo da Wikipedia sobre recursão!

Answer 9

1. Uma função que chama a si mesma
2. Quando uma função pode ser (facilmente) decomposta em uma operação simples mais a mesma função em alguma parte menor do problema.Devo dizer, antes, que isso o torna um bom candidato à recursão.
3. Eles fazem!

O exemplo canônico é o fatorial que se parece com:

int fact(int a) 
{
  if(a==1)
    return 1;

  return a*fact(a-1);
}

Em geral, a recursão não é necessariamente rápida (a sobrecarga de chamada de função tende a ser alta porque as funções recursivas tendem a ser pequenas, veja acima) e pode sofrer de alguns problemas (alguém está com estouro de pilha?).Alguns dizem que tendem a ser difíceis de acertar em casos não triviais, mas eu realmente não acredito nisso.Em algumas situações, a recursão faz mais sentido e é a maneira mais elegante e clara de escrever uma função específica.Deve-se notar que algumas linguagens favorecem soluções recursivas e as otimizam muito mais (vem à mente LISP).

Answer 10

Uma função recursiva é aquela que chama a si mesma.O motivo mais comum que descobri para usá-lo é atravessar uma estrutura em árvore.Por exemplo, se eu tiver um TreeView com caixas de seleção (pense na instalação de um novo programa, na página "escolha os recursos para instalar"), talvez eu queira um botão "marcar tudo", que seria algo assim (pseudocódigo):

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

function checkRecursively(Node n) {
    n.Checked = True;
    foreach ( n.Children as child ) {
        checkRecursively(child);
    }
}

Portanto, você pode ver que checkRecursively primeiro verifica o nó pelo qual foi passado e, em seguida, chama a si mesmo para cada um dos filhos desse nó.

Você precisa ter um pouco de cuidado com a recursão.Se você entrar em um loop recursivo infinito, receberá uma exceção Stack Overflow :)

Não consigo pensar em uma razão pela qual as pessoas não devam usá-lo, quando apropriado.É útil em algumas circunstâncias e não em outras.

Acho que por ser uma técnica interessante, alguns programadores talvez acabem usando-a com mais frequência do que deveriam, sem justificativa real.Isso deu à recursão uma má reputação em alguns círculos.

Answer 11

Recursão é uma expressão que se refere direta ou indiretamente a si mesma.

Considere siglas recursivas como um exemplo simples:

• GNU apoia GNU não é Unix
• PHP apoia PHP:Pré-processador de hipertexto
• YAML apoia YAML não é linguagem de marcação
• VINHO apoia Wine não é um emulador
• VISTO apoia Associação de serviço internacional Visa

Mais exemplos na Wikipédia

Answer 12

A recursão funciona melhor com o que gosto de chamar de "problemas fractais", onde você está lidando com algo grande feito de versões menores dessa coisa grande, cada uma das quais é uma versão ainda menor da coisa grande, e assim por diante.Se você precisar percorrer ou pesquisar algo como uma árvore ou estruturas idênticas aninhadas, terá um problema que pode ser um bom candidato para recursão.

As pessoas evitam a recursão por vários motivos:

1. A maioria das pessoas (inclusive eu) começou a trabalhar na programação processual ou orientada a objetos, em oposição à programação funcional.Para essas pessoas, a abordagem iterativa (normalmente usando loops) parece mais natural.

2. Aqueles de nós que começaram a programar em programação processual ou orientada a objetos muitas vezes foram instruídos a evitar a recursão porque ela é propensa a erros.

3. Muitas vezes ouvimos que a recursão é lenta.Chamar e retornar de uma rotina repetidamente envolve muito push e popping de pilha, o que é mais lento que o loop.Acho que algumas linguagens lidam com isso melhor do que outras, e essas linguagens provavelmente não são aquelas em que o paradigma dominante é processual ou orientado a objetos.

4. Em pelo menos algumas linguagens de programação que usei, lembro-me de ouvir recomendações para não usar recursão se ela ultrapassar uma certa profundidade porque sua pilha não é tão profunda.

Answer 13

Uma declaração recursiva é aquela em que você define o processo do que fazer a seguir como uma combinação das entradas e do que você já fez.

Por exemplo, pegue o fatorial:

factorial(6) = 6*5*4*3*2*1

Mas é fácil ver que factorial(6) também é:

6 * factorial(5) = 6*(5*4*3*2*1).

Então geralmente:

factorial(n) = n*factorial(n-1)

É claro que o aspecto complicado da recursão é que, se você quiser definir as coisas em termos do que já fez, é necessário que haja algum lugar por onde começar.

Neste exemplo, apenas criamos um caso especial definindo factorial(1) = 1.

Agora vemos isso de baixo para cima:

factorial(6) = 6*factorial(5)
                   = 6*5*factorial(4)
                   = 6*5*4*factorial(3) = 6*5*4*3*factorial(2) = 6*5*4*3*2*factorial(1) = 6*5*4*3*2*1

Como definimos factorial(1) = 1, chegamos ao "fundo".

De modo geral, os procedimentos recursivos têm duas partes:

1) A parte recursiva, que define algum procedimento em termos de novas entradas combinadas com o que você “já fez” através do mesmo procedimento.(ou seja, factorial(n) = n*factorial(n-1))

2) Uma parte básica, que garante que o processo não se repita para sempre, dando-lhe um ponto de partida (ou seja, factorial(1) = 1)

Pode ser um pouco confuso entender no início, mas basta olhar para um monte de exemplos e tudo deve se encaixar.Se você quiser uma compreensão muito mais profunda do conceito, estude indução matemática.Além disso, esteja ciente de que algumas linguagens otimizam chamadas recursivas, enquanto outras não.É muito fácil criar funções recursivas incrivelmente lentas se você não tomar cuidado, mas também existem técnicas para torná-las eficientes na maioria dos casos.

Espero que isto ajude...

Answer 14

Eu gosto desta definição:
Na recursão, uma rotina resolve ela mesma uma pequena parte de um problema, divide o problema em partes menores e depois chama a si mesma para resolver cada uma das partes menores.

Também gosto da discussão de Steve McConnell sobre recursão em Code Complete, onde ele critica os exemplos usados ​​em livros de Ciência da Computação sobre Recursão.

Não use recursão para fatoriais ou números de Fibonacci

Um problema com os livros didáticos da ciência da computação é que eles apresentam exemplos tolos de recursão.Os exemplos típicos estão calculando uma fatorial ou calculando uma sequência de Fibonacci.A recursão é uma ferramenta poderosa, e é realmente idiota usá -la em qualquer um desses casos.Se um programador que trabalhou para mim usasse a recursão para calcular uma fatorial, eu contrataria outra pessoa.

Achei que este era um ponto muito interessante a ser levantado e pode ser a razão pela qual a recursão é frequentemente mal compreendida.

EDITAR:Isso não foi uma crítica à resposta de Dav - eu não tinha visto essa resposta quando postei isso

Answer 15

1.) Um método é recursivo se puder se chamar;diretamente:

void f() {
   ... f() ... 
}

ou indiretamente:

void f() {
    ... g() ...
}

void g() {
   ... f() ...
}

2.) Quando usar recursão

Q: Does using recursion usually make your code faster? 
A: No.
Q: Does using recursion usually use less memory? 
A: No.
Q: Then why use recursion? 
A: It sometimes makes your code much simpler!

3.) As pessoas usam recursão apenas quando é muito complexo escrever código iterativo.Por exemplo, técnicas de travessia de árvore, como pré-encomenda e pós-ordem, podem ser tornadas iterativas e recursivas.Mas geralmente usamos recursivo devido à sua simplicidade.

Answer 16

Aqui está um exemplo simples:quantos elementos em um conjunto.(existem maneiras melhores de contar coisas, mas este é um bom exemplo recursivo simples.)

Primeiro, precisamos de duas regras:

1. se o conjunto estiver vazio, a contagem de itens no conjunto será zero (duh!).
2. se o conjunto não estiver vazio, a contagem será um mais o número de itens no conjunto após a remoção de um item.

Suponha que você tenha um conjunto como este:[x x x].vamos contar quantos itens existem.

1. o conjunto é [x x x] que não está vazio, então aplicamos a regra 2.o número de itens é um mais o número de itens em [x x] (ou seja,removemos um item).
2. o conjunto é [x x], então aplicamos a regra 2 novamente:um + número de itens em [x].
3. o conjunto é [x], que ainda corresponde à regra 2:um + número de itens em [].
4. Agora o conjunto é [], que corresponde à regra 1:a contagem é zero!
5. Agora que sabemos a resposta na etapa 4 (0), podemos resolver a etapa 3 (1 + 0)
6. Da mesma forma, agora que sabemos a resposta na etapa 3 (1), podemos resolver a etapa 2 (1 + 1)
7. E finalmente agora que sabemos a resposta na etapa 2 (2), podemos resolver a etapa 1 (1 + 2) e obter a contagem de itens em [x x x], que é 3.Viva!

Podemos representar isso como:

count of [x x x] = 1 + count of [x x]
                 = 1 + (1 + count of [x])
                 = 1 + (1 + (1 + count of []))
                 = 1 + (1 + (1 + 0)))
                 = 1 + (1 + (1))
                 = 1 + (2)
                 = 3

Ao aplicar uma solução recursiva, normalmente você tem pelo menos 2 regras:

• a base, o caso simples que indica o que acontece quando você "esgota" todos os seus dados.Geralmente é uma variação de "se você não tiver dados para processar, sua resposta é X"
• a regra recursiva, que indica o que acontece se você ainda tiver dados.Geralmente é algum tipo de regra que diz "faça algo para diminuir seu conjunto de dados e reaplique suas regras ao conjunto de dados menor".

Se traduzirmos o texto acima para pseudocódigo, obteremos:

numberOfItems(set)
    if set is empty
        return 0
    else
        remove 1 item from set
        return 1 + numberOfItems(set)

Há muitos outros exemplos úteis (atravessar uma árvore, por exemplo) que tenho certeza que outras pessoas irão abordar.

Answer 17

Bem, essa é uma definição bastante decente que você tem.E a Wikipedia também tem uma boa definição.Então acrescentarei outra definição (provavelmente pior) para você.

Quando as pessoas se referem a "recursão", geralmente estão falando sobre uma função que escreveram, que chama a si mesma repetidamente até terminar seu trabalho.A recursão pode ser útil ao percorrer hierarquias em estruturas de dados.

Answer 18

Um exemplo:Uma definição recursiva de escada é:Uma escada consiste em:- Uma única etapa e uma escada (recursão) - ou apenas uma única etapa (terminação)

Answer 19

Para recorrer a um problema resolvido:não faça nada, está feito.
Para recorrer a um problema aberto:faça o próximo passo e repita o resto.

Answer 20

Em inglês simples:Suponha que você possa fazer três coisas:

1. Pegue uma maçã
2. Anote as marcas de registro
3. Contar marcas de contagem

Você tem muitas maçãs à sua frente em uma mesa e quer saber quantas maçãs existem.

start
  Is the table empty?
  yes: Count the tally marks and cheer like it's your birthday!
  no:  Take 1 apple and put it aside
       Write down a tally mark
       goto start

O processo de repetir a mesma coisa até terminar é chamado de recursão.

Espero que esta seja a resposta em "inglês simples" que você está procurando!

Answer 21

Uma função recursiva é uma função que contém uma chamada para si mesma.Uma estrutura recursiva é uma estrutura que contém uma instância de si mesma.Você pode combinar os dois como uma classe recursiva.A parte principal de um item recursivo é que ele contém uma instância/chamada de si mesmo.

Considere dois espelhos um de frente para o outro.Vimos o belo efeito de infinito que eles produzem.Cada reflexão é uma instância de espelho, que está contida em outra instância de espelho, etc.O espelho que contém um reflexo de si mesmo é a recursão.

A árvore de pesquisa binária é um bom exemplo de programação de recursão.A estrutura é recursiva com cada nó contendo 2 instâncias de um nó.Funções para trabalhar em uma árvore de pesquisa binária também são recursivas.

Answer 22

Esta é uma pergunta antiga, mas quero adicionar uma resposta do ponto de vista logístico (ou seja, não do ponto de vista da correção do algoritmo ou do ponto de vista do desempenho).

Eu uso Java para trabalhar e Java não oferece suporte a funções aninhadas.Dessa forma, se eu quiser fazer recursão, talvez precise definir uma função externa (que existe apenas porque meu código esbarra nas regras burocráticas do Java) ou talvez precise refatorar o código completamente (o que eu realmente odeio fazer).

Assim, muitas vezes evito a recursão e, em vez disso, uso a operação de pilha, porque a recursão em si é essencialmente uma operação de pilha.

Answer 23

Você deseja usá-lo sempre que tiver uma estrutura em árvore.É muito útil na leitura de XML.

Answer 24

A recursão aplicada à programação é basicamente chamar uma função de dentro de sua própria definição (dentro de si mesma), com parâmetros diferentes para realizar uma tarefa.

Answer 25

"Se eu tiver um martelo, faça tudo parecer um prego."

A recursão é uma estratégia de resolução de problemas para enorme problemas, onde a cada passo basta "transformar 2 coisas pequenas em uma coisa maior", cada vez com o mesmo martelo.

Exemplo

Suponha que sua mesa esteja coberta com uma bagunça desorganizada de 1.024 papéis.Como você cria uma pilha de papéis organizada e limpa da bagunça, usando recursão?

1. Dividir: Espalhe todas as folhas, de modo que você tenha apenas uma folha em cada “pilha”.
2. Conquistar:
   2. Dê a volta, colocando cada folha em cima de outra folha.Agora você tem pilhas de 2.
   3. Dê a volta, colocando cada pilha de 2 em cima de outra pilha de 2.Agora você tem pilhas de 4.
   4. Dê a volta, colocando cada pilha de 4 em cima de outra pilha de 4.Agora você tem pilhas de 8.
   5. ...assim por diante...
   6. Agora você tem uma pilha enorme de 1.024 folhas!

Observe que isso é bastante intuitivo, além de contar tudo (o que não é estritamente necessário).Você pode não chegar até as pilhas de 1 folha, na realidade, mas poderia e ainda funcionaria.A parte importante é o martelo:Com os braços, você sempre pode colocar uma pilha em cima da outra para fazer uma pilha maior, e não importa (dentro do razoável) o tamanho de cada pilha.

Answer 26

Recursão é o processo em que um método chama a si mesmo para poder realizar uma determinada tarefa.Reduz a redundância de código.A maioria das funções ou métodos recursivos devem ter uma condição para interromper a chamada recursiva, ou seja,impedi-lo de chamar a si mesmo se uma condição for atendida - isso evita a criação de um loop infinito.Nem todas as funções são adequadas para uso recursivo.

Answer 27

ei, desculpe se minha opinião concorda com alguém, só estou tentando explicar a recursão em inglês simples.

suponha que você tenha três gerentes - Jack, John e Morgan.Jack gerencia 2 programadores, John - 3 e Morgan - 5.você vai dar a cada gerente 300$ e quer saber quanto custaria.A resposta é óbvia – mas e se dois dos funcionários da Morgan também forem gestores?

AQUI vem a recursão.você começa do topo da hierarquia.o custo de verão é 0$.Você começa com Jack e verifica se ele tem algum gerente como funcionários.se você descobrir que algum deles é, verifique se eles têm algum gerente como funcionário e assim por diante.Adicione 300$ ao custo de verão sempre que encontrar um gerente.quando terminar com Jack, vá até John, seus funcionários e depois até Morgan.

Você nunca saberá quantos ciclos percorrerá antes de obter uma resposta, embora saiba quantos gerentes tem e quanto orçamento pode gastar.

A recursão é uma árvore, com galhos e folhas, chamados pais e filhos respectivamente.Ao usar um algoritmo de recursão, você está mais ou menos conscientemente construindo uma árvore a partir dos dados.

Answer 28

Em inglês simples, recursão significa repetir algo continuamente.

Na programação, um exemplo é chamar a função dentro dela mesma.

Veja o seguinte exemplo de cálculo do fatorial de um número:

public int fact(int n)
{
    if (n==0) return 1;
    else return n*fact(n-1)
}

Answer 29

Qualquer algoritmo exibe estrutural a recursão em um tipo de dados if consiste basicamente em uma instrução switch com um case para cada caso do tipo de dados.

por exemplo, quando você está trabalhando em um tipo

  tree = null 
       | leaf(value:integer) 
       | node(left: tree, right:tree)

um algoritmo recursivo estrutural teria a forma

 function computeSomething(x : tree) =
   if x is null: base case
   if x is leaf: do something with x.value
   if x is node: do something with x.left,
                 do something with x.right,
                 combine the results

esta é realmente a maneira mais óbvia de escrever qualquer algoritmo que funcione em uma estrutura de dados.

agora, quando você olha para os inteiros (bem, os números naturais) conforme definidos usando os axiomas de Peano

 integer = 0 | succ(integer)

você vê que um algoritmo recursivo estrutural em números inteiros se parece com isto

 function computeSomething(x : integer) =
   if x is 0 : base case
   if x is succ(prev) : do something with prev

A função fatorial muito conhecida é o exemplo mais trivial desse formulário.

Answer 30

função chama a si mesma ou usa sua própria definição.