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

votos
121

Um dos temas que parece vir-se regularmente em listas de discussão e debates online é os méritos (ou falta dela) de fazer uma Ciências Licenciatura da Computação. Um argumento que parece vir-se uma e outra vez para a festa negativo é que eles foram codificação para um determinado número de anos e eles nunca usou a recursividade.

Então a questão é:

  1. O que é recursão?
  2. Quando usar recursão?
  3. Por que as pessoas não usam recursão?
Publicado 06/08/2008 em 03:29
fonte usuário
Em outras línguas...                            


40 respostas

votos
86

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

Para ver por que, percorrer as etapas que as línguas acima usam para chamar uma função:

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

Fazendo todas essas etapas leva tempo, geralmente um pouco mais do que leva para percorrer um loop. No entanto, o verdadeiro problema é na etapa # 1. Quando muitos programas começar, eles alocar um único pedaço de memória para o seu stack, e quando eles saem de que a memória (muitas vezes, mas nem sempre devido a recursão), o programa trava devido a um estouro de pilha .

Assim, em línguas recursão é mais lento e isso o torna vulnerável a falhas. Há ainda alguns argumentos para usá-lo embora. Em geral, o código escrito de forma recursiva é mais curto e um pouco mais elegante, uma vez que você sabe como lê-lo.

Há uma técnica que os implementadores de linguagem pode usar o chamado otimização de chamada de cauda que pode eliminar algumas classes de estouro de pilha. Coloque sucintamente: se expressão de retorno de uma função é simplesmente o resultado de uma chamada de função, então você não precisa adicionar um novo nível na pilha, você pode reutilizar o atual para a função que está sendo chamado. Lamentavelmente, alguns imperativas de linguagem implementações têm otimização de chamada incorporado.

* Eu amo a recursividade. Minha linguagem estática favorito não usar loops em tudo, a recursividade é a única maneira de fazer alguma coisa repetidamente. Eu só não acho que a recursividade é geralmente uma boa idéia em idiomas que não estão sintonizados para ele.

** A propósito Mario, o nome típico para a sua função ArrangeString é "juntar-se", e eu ficaria surpreso se o seu idioma de escolha ainda não tem uma implementação do mesmo.

Respondeu 06/08/2008 em 06:09
fonte usuário

votos
63

exemplo Inglês simples de recursão.

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.
Respondeu 04/05/2010 em 17:38
fonte usuário

votos
49

No sentido informática mais básica, a recursividade é uma função que se chama. Digamos que você tenha uma estrutura lista ligada:

struct Node {
    Node* next;
};

E você quer saber quanto tempo uma lista ligada é que você pode fazer isso com recursão:

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

(Isto poderia, obviamente, ser feito com um loop for bem, mas é útil como uma ilustração do conceito)

Respondeu 04/05/2010 em 12:25
fonte usuário

votos
46

Sempre que uma função chama a si mesmo, criando um loop, então isso é recursão. Como com qualquer coisa, há bons usos e maus usos para a recursividade.

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

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

No entanto, este é um coxo exemplo, quase inútil, porque ele pode ser facilmente substituído por iteração mais eficiente. Depois de tudo, a recursividade sofre de sobrecarga de chamada de função, o que no exemplo acima pode ser substancial em comparação com a operação no interior da própria função.

Assim, toda a razão para fazer recursão em vez de iteração deve ser o de aproveitar a pilha de chamadas para fazer alguma coisa inteligente. Por exemplo, se você chamar uma função várias vezes com parâmetros diferentes dentro do mesmo circuito, então isso é uma maneira de realizar ramificação . Um exemplo clássico é o triângulo Sierpinsky .

digite descrição da imagem aqui

Você pode desenhar um daqueles muito simplesmente com recursão, onde os ramos pilha de chamadas 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 iteração Eu acho que você vai encontrá-lo leva um código mais muito a realizar.

Outros casos de uso comum podem incluir hierarquias atravessam, rastreadores por exemplo, website, comparações de diretório, etc.

Conclusão

Em termos práticos, recursão faz mais sentido sempre que precisar ramificação iterativo.

Respondeu 04/05/2010 em 14:33
fonte usuário

votos
28

Recursão é um método de resolver problemas com base no dividir e conquistar mentalidade. A idéia básica é que você tome o problema original e dividi-lo em pequenos (mais facilmente resolvidos) instâncias de si mesmo, resolver esses casos menores (geralmente usando o mesmo algoritmo de novo) e depois remontá-las na solução final.

O exemplo clássico é uma rotina para gerar o factorial de n. O factorial de n é calculado multiplicando todos os números entre 1 e n. Uma solução iterativa em C # parece com isso:

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

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

  return fact;
}

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

A solução recursiva é encontrado pelo reconhecimento de que a enésima Factorial é n * Fato (n-1). Ou, dito de outra forma, se você sabe o que um número fatorial particular é que você pode calcular a próxima. 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 Guard) e é o que impede o algoritmo de correr para sempre. Ele só retorna o valor 1 sempre que a função é chamada com um valor de 1 ou menos. A segunda parte é mais interessante e é conhecido como o Passo recursiva . Aqui nós chamamos o mesmo método com um parâmetro ligeiramente modificada (que diminuí-lo por 1) e, em seguida, multiplicar o resultado com a nossa cópia do n.

Quando encontrou pela primeira vez isso pode ser meio confuso por isso é instrutivo examinar como funciona quando executado. Imagine que nós chamamos FactRec (5). Nós entramos na rotina, não são apanhados pelo caso base e assim vamos acabar com isto:

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

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

Se nós re-introduzir o método com o parâmetro 4 nós de novo não são interrompidos pela cláusula de guarda e por isso, acabam em:

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

Se substituirmos este valor de retorno para o valor de retorno acima obtemos

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

Isso deve lhe dar uma idéia de como a solução final se chega a isso vamos fast track e mostrar cada passo no caminho para baixo:

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

Que a substituição definitiva acontece quando o caso base é acionado. Neste momento temos uma fórmula algrebraic simples de resolver o que equivale diretamente para a definição de fatoriais em primeiro lugar.

É instrutivo notar que todas as chamadas para os resultados do método em qualquer um caso base que está sendo acionado ou uma chamada para o mesmo método em que os parâmetros estão mais próximos de um caso base (muitas vezes chamado de uma chamada recursiva). Se este não for o caso, então o método será executado para sempre.

Respondeu 06/08/2008 em 03:54
fonte usuário

votos
12

Recursão está resolvendo um problema com uma função que se chama. Um bom exemplo disto é uma função factorial. Factorial é um problema de matemática onde factorial de 5, por exemplo, é de 5 * 4 * 3 * 2 * 1. Esta função resolve este em C # para inteiros positivos (não testado - pode haver um erro).

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

    return n * Factorial(n - 1);
}
Respondeu 04/05/2010 em 12:29
fonte usuário

votos
9

Considere um problema antigo, bem conhecido :

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

A definição de gcd é surpreendentemente simples:

definição gcd

onde mod é o operador módulo (ou seja, o restante após a divisão inteira).

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

Se você gostaria de saber por que isso funciona, consulte o artigo da Wikipedia sobre o algoritmo de Euclides .

Vamos calcular GCD (10, 8), como um exemplo. Cada passo é igual ao que pouco antes de ele:

  1. GCD (10, 8)
  2. GCD (10, 10 mod 8)
  3. GCD (8, 2)
  4. GCD (8, 8 mod 2)
  5. GCD (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 8 porque vai para 10, uma vez com um resto de 2. No passo 3, a segunda parte aplica-se novamente, mas desta vez de 8 mod 2 = 0 porque duas divisões 8 sem resto. Na etapa 5, o segundo argumento é 0, então a resposta é 2.

Você notou que gcd aparece em ambos os 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 se repete dentro de sua definição.

definições recursivos tendem a ser elegante. 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 em uma lista e tailé o resto da lista. Note-se que sumse repete dentro de sua definição no final.

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

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 de forma recursiva para transformá-lo em uma série de adições:

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

Se isso pouco sobre transformando multiplicação em uma série de adições não faz sentido, tente expandir alguns exemplos simples para ver como ele funciona.

Merge sort tem uma bela 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 toda parte, se você sabe o que procurar. Note como todas estas definições têm casos de bases muito simples, por exemplo , GCD (m, 0) = m. O casos recursiva esculpir o problema para chegar até as respostas fáceis.

Com esse entendimento, agora você pode apreciar os outros algoritmos em artigo da Wikipedia sobre a recursividade !

Respondeu 04/05/2010 em 14:58
fonte usuário

votos
9

Recursão refere-se a um método que resolve um problema por resolver uma versão mais pequena do problema e, em seguida, utilizando aquele resultado mais algum outro cálculo para formular a resposta para o problema original. Muitas vezes, no processo de resolver a versão menor, o método vai resolver uma versão ainda menor do problema, e assim por diante, até atingir um "caso base" que é trivial para resolver.

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 de "recurses" para encontrar o fatorial de X-1, em seguida, multiplica o que quer que tem por Xdar uma resposta final. Claro que, para encontrar o fatorial de X-1, ele vai 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 para retornar 1uma vez 0! = 1! = 1.

Respondeu 04/05/2010 em 12:26
fonte usuário

votos
9
  1. Uma função que se chama
  2. Quando uma função pode ser (facilmente) decomposta em uma operação simples, além de a mesma função em alguns porção menor do problema. Devo dizer, sim, que isso o torna um bom candidato para a recursividade.
  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ápido (sobrecarga chamada de função tende a ser elevada, porque recursiva funções tendem a ser pequenos, ver acima) e pode sofrer de alguns problemas (stack overflow alguém?). Alguns dizem que eles tendem a ser difíceis de obter 'direito' em casos não-triviais, mas eu realmente não comprar em que. Em algumas situações, recursão faz mais sentido e é a maneira mais elegante e claro para escrever uma função particular. Deve-se notar que algumas linguagens de favorecer soluções recursivas e otimizá-los muito mais (LISP vem à mente).

Respondeu 06/08/2008 em 03:35
fonte usuário

votos
7

A função recursiva é aquela que se chama. A razão mais comum que eu encontrei para usá-lo está atravessando uma estrutura de árvore. Por exemplo, se eu tenho um TreeView com caixas de seleção (acho que a instalação de um novo programa "escolha recursos para instalar" página), eu poderia querer um botão "verificar todos", que seria algo como este (pseudocódigo):

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

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

Assim você pode ver que o checkRecursively primeiro verifica o nó que ele é passado, em seguida, chama-se para cada um dos filhos desse nó.

Você precisa ser um pouco cuidadoso com recursividade. Se você entrar em um loop recursivo infinito, você receberá uma exceção de estouro de pilha :)

Eu não consigo pensar em uma razão pela qual as pessoas não devem usá-lo, quando for o caso. É útil em algumas circunstâncias, e não em outros.

Eu acho que porque é uma técnica interessante, alguns programadores talvez acabar de usá-lo com mais freqüência do que deveriam, sem justificação real. Isso deu recursão um mau nome em alguns círculos.

Respondeu 06/08/2008 em 03:44
fonte usuário

votos
5

Recursão é uma expressão referenciando-se direta ou indiretamente.

Considere acrônimo recursivo como um exemplo simples:

  • GNU significa do GNU Not Unix
  • PHP significa PHP: Hypertext Preprocessor
  • YAML significa YAML Is not Markup Language
  • VINHO significa Wine Is Not an Emulator
  • VISA significa Visa International Service Association

Mais exemplos na Wikipedia

Respondeu 04/05/2010 em 12:56
fonte usuário

votos
5

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

Primeiro, precisamos de duas regras:

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

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

  1. o conjunto é [XXX] que não está vazia, de modo que se aplicam regra 2. o número de itens é uma mais o número de itens na [XX] (ou seja, que removeu um item).
  2. o conjunto é [xx], então eu aplico a regra 2 novamente: número um + de itens em [x].
  3. o conjunto é [x], que ainda corresponde a regra 2: um número + de itens em [].
  4. Agora, o conjunto é [], o que corresponde a 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 no passo 3 (1), podemos resolver a etapa 2 (1 + 1)
  7. E, finalmente, agora que sabemos a resposta na etapa 2 (2), podemos resolver passo 1 (1 + 2) e obter a contagem de itens em [xxx], que é 3. Hooray!

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, você geralmente tem pelo menos 2 regras:

  • a base, o caso simples que afirma o que acontece quando você tem "usado" todos os seus dados. Isso geralmente é alguma variação de "se você estiver fora de dados para processar, a sua resposta é X"
  • a regra recursiva, que diz o que acontece se você ainda tiver dados. Isso geralmente é algum tipo de regra que diz que "fazer algo para tornar seu conjunto de dados menor, e reaplicar suas regras para o conjunto de dados menor."

Se traduzirmos o acima para pseudocódigo, temos:

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

Há muito mais exemplos úteis (atravessando uma árvore, por exemplo), que eu tenho certeza que outras pessoas vão cobrir.

Respondeu 06/08/2008 em 04:12
fonte usuário

votos
5

Recursão funciona melhor com o que eu gosto de chamar de "problemas do Fractal", onde você está lidando com uma coisa grande que é feito de versões menores de tão grande coisa, cada um dos quais é uma versão ainda menor da grande coisa, e assim por diante. Se alguma vez tiver que atravessar ou busca através de algo como uma árvore ou estruturas idênticas aninhados, você tem um problema que pode ser um bom candidato para a recursividade.

Pessoas evitar recursão para um número de razões:

  1. A maioria das pessoas (eu incluído) cortou seus dentes programação em programação procedural ou orientada a objeto em oposição a programação funcional. Para essas pessoas, a abordagem iterativa (normalmente usando loops) se sente mais natural.

  2. Aqueles de nós que cortar os dentes de programação na programação procedural ou orientada a objeto têm sido muitas vezes dito para evitar recursão porque é propenso a erros.

  3. Estamos disse muitas vezes que a recursividade é lento. Chamada e retorno de uma rotina repetidamente envolve um monte de pilha empurrando e popping, que é mais lento do que looping. Eu acho que algumas linguagens de lidar com isso melhor do que outros, e essas línguas são mais provável não aqueles em que o paradigma dominante é processual ou orientada a objeto.

  4. Por pelo menos um par de linguagens de programação que usei, lembro-me recomendações ouvir não usar recursividade se ele fica para além de uma certa profundidade, porque a sua pilha não é tão profundo.

Respondeu 06/08/2008 em 04:12
fonte usuário

votos
4

1.) Um método é recursiva se pode chamar-se; quer directamente:

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 somente quando é muito complexo para escrever o código iterativo. Por exemplo, as técnicas de passagem de árvore como pré-venda, pós-ordem pode ser feita tanto iterativa e recursiva. Mas geralmente usamos recursiva devido à sua simplicidade.

Respondeu 11/03/2014 em 10:47
fonte usuário

votos
4

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

Por exemplo, pegue fatorial:

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

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

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

Assim, em geral:

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

Claro, a coisa complicada sobre recursão é que se você quer definir as coisas em termos do que você já fez, é preciso haver algum lugar para começar.

Neste exemplo, nós apenas fazer um caso especial através da definição de fatorial (1) = 1.

Agora vamos vê-lo 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

Desde que definimos fatorial (1) = 1, chegamos ao "fundo".

De um modo geral, os procedimentos recursiva tem duas partes:

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

2) A parte de base, que garante que o processo não repetir para sempre, dando-lhe algum lugar para começar (ou seja factorial(1) = 1)

Pode ser um pouco confuso para obter a sua cabeça em torno no início, mas basta olhar para um monte de exemplos e deve vir todos juntos. Se você quer uma compreensão muito mais profunda do conceito, estudar a indução matemática. Além disso, estar ciente de que algumas línguas otimizar para chamadas recursivas, enquanto outros não. É muito fácil de fazer funções recursivas insanamente lentos se você não tiver cuidado, mas também existem técnicas para torná-los performance na maioria dos casos.

Espero que isto ajude...

Respondeu 04/05/2010 em 14:30
fonte usuário

votos
4

Gosto dessa definição:
Em recursão, uma rotina resolve uma pequena parte de um problema em si, divide o problema em partes menores e, em seguida, chama-se para resolver cada uma das peças mais pequenas.

Também gosto de Steve McConnells discussão de recursão no código completo, onde ele critica os exemplos usados ​​nos livros de Ciência da Computação na recursão.

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

Um problema com os livros-ciência da computação é que eles apresentam exemplos bobos de recursão. Os exemplos típicos são computação um factorial ou calcular uma sequência de Fibonacci. Recursão é uma ferramenta poderosa, e é realmente mudo de usá-lo em qualquer desses casos. Se um programador que trabalhou para mim utilizado recursão para calcular um fatorial, eu contrataria alguém.

Eu pensei que este era um ponto muito interessante para levantar e pode ser uma razão pela qual a recursividade é muitas vezes incompreendido.

EDIT: Esta não foi uma escavação em resposta de Dav - Eu não tinha visto essa resposta quando eu postei isso

Respondeu 04/05/2010 em 12:29
fonte usuário

votos
3

Um exemplo: Uma definição recursiva de uma escadaria é: Uma escada constituída por: - um único passo e uma escada (recursão) - ou apenas um único passo (terminação)

Respondeu 04/05/2010 em 14:34
fonte usuário

votos
3

Bem, isso é uma definição bastante decente que você tem. E wikipedia tem uma boa definição também. Então, eu vou adicionar outra (provavelmente pior) a definição para você.

Quando as pessoas se referem a "recursão", eles são geralmente falando sobre uma função que tenha escrito que se chama repetidamente até que seja feito com o seu trabalho. Recursão pode ser útil quando atravessando as hierarquias em estruturas de dados.

Respondeu 04/05/2010 em 12:27
fonte usuário

votos
3

Para recurse em um problema resolvido: não fazer nada, você está feito.
Para recurse em um problema em aberto: fazer o próximo passo, então recurse sobre o resto.

Respondeu 06/08/2008 em 04:32
fonte usuário

votos
2

Esta é uma questão de idade, mas eu quero adicionar uma resposta do ponto de vista logístico (ou seja, não a partir do ponto algoritmo de correção de visão ou ponto de vista do desempenho).

Eu uso Java para o trabalho, e Java não suporta a função aninhada. Como tal, se eu quero fazer recursão, eu poderia ter de definir uma função externa (que só existe porque o meu código esbarra contra o regime burocrático de Java), ou eu poderia ter para refatorar o código completamente (o que eu realmente odeio fazer).

Assim, muitas vezes eu evitar recursão, e operação uso de pilha em vez disso, porque a própria recursão é essencialmente uma operação de pilha.

Respondeu 30/08/2014 em 11:09
fonte usuário

votos
2

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

Considere dois espelhos voltados um para o outro. Nós vimos o efeito infinito puro que eles fazem. Cada reflexão é um exemplo de um espelho, o qual está contido dentro de um outro exemplo de um espelho, etc. O espelho que contém uma reflexão de si é recursão.

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

Respondeu 04/05/2010 em 17:46
fonte usuário

votos
2

Na planície Inglês: Suponha que você pode fazer 3 coisas:

  1. Pegue uma maçã
  2. Anote marcas de registro
  3. Contagem marcas de registro

Você tem um monte de maçãs na frente de você sobre uma mesa e você 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é que você é feito é chamado recursão.

Espero que este é o "Inglês plain" resposta que você está procurando!

Respondeu 04/05/2010 em 14:09
fonte usuário

votos
1

A definição mais simples de recursão é "auto-referência". Uma função que refere-se a si mesmo, ou seja, chamadas em si é recursivo. A coisa mais importante a ter em mente, é que uma função recursiva deve ter um "caso base", ou seja, uma condição que se for verdade faz com que ele não se chamar, e, assim, terminar a recursão. Caso contrário, terá recursividade infinita:

recursão http://cart.kolix.de/wp-content/uploads/2009/12/infinite-recursion.jpg

Respondeu 04/05/2010 em 17:10
fonte usuário

votos
1

Recursividade é quando você tem uma operação que se usa. Ele provavelmente terá um ponto de parada, caso contrário ele iria durar para sempre.

Vamos dizer que você quer procurar uma palavra no dicionário. Você tem uma operação chamada "look-up" à sua disposição.

Seu amigo diz: "Eu realmente poderia colher um pouco de pudim de agora!" Você não sabe o que ele significa, então você olhar para cima "colher" no dicionário, e lê algo como isto:

Colher: substantivo - um utensílio com uma colher redonda no final. Colher: verbo - para usar uma colher em algo colher: verbo - para cuidar de perto por trás

Agora, sendo que você não é muito bom com o Inglês, isso aponta na direção certa, mas você precisa de mais informações. Então você selecione "utensílio" e "carinho" para procurar por mais algumas informações.

Cuddle: verbo - para aconchegar utensílio: substantivo - uma ferramenta, muitas vezes, um utensílio comer

Ei! Você sabe o aconchego é, e não tem nada a ver com pudim. Você também sabe que pudim é algo que você come, por isso faz sentido agora. Seu amigo deve querer comer o pudim com uma colher.

Ok, ok, este foi um exemplo muito coxo, mas ilustra (talvez mal) as duas partes principais da recursividade. 1) Ele usa-se. Neste exemplo, você realmente não olhou para cima uma palavra significativamente até entendê-lo, e isso pode significar olhando para cima mais palavras. Isso nos leva ao ponto dois, 2) Ele pára em algum lugar. Tem que ter algum tipo de caso-base. Caso contrário, você só acabam olhando para cima cada palavra no dicionário, o que provavelmente não é muito útil. O nosso caso base foi que você tem informações suficientes para fazer uma conexão entre o que você já fez e não entendia.

O exemplo que é dado tradicional é fatorial, onde 5 é fatorial 1 * 2 * 3 * 4 * 5 (que é de 120). A base de caso seria 0 (ou 1, dependendo). Assim, para qualquer número inteiro n, você faz o seguinte

é n igual a 0? retornar um outro modo, o retorno n * (fatorial de n-1)

vamos fazer isso com o exemplo de 4 (que sabemos antes do tempo é 1 * 2 * 3 * 4 = 24).

fatorial de 4 ... é 0? não, por isso deve ser 4 * fatorial de 3, mas o que é fatorial de 3? é 3 * fatorial de 2 fatorial de 2 é 2 * fatorial de 1 factorial de 1 é 1 * fatorial de 0 e sabemos fatorial de 0! :-D é 1, que é o fatorial definição de 1 a 1 * fatorial de 0, que foi de 1 ... assim 1 * 1 = 1 fatorial de 2 é 2 * factorial de 1, que foi de 1 ... então 2 * 1 = 2 3 factorial de 3 é * factorial de 2, que foi de 2 ... então 3 * 2 = 6 factorial de 4 (finalmente !!) é 4 * factorial de três, que foi de 6 ... 4 * 6 é 24

Fatorial é um simples caso de "caso base, e usa-se".

Agora, observe que ainda estavam trabalhando em fatorial de 4 toda a maneira para baixo ... Se quiséssemos fatorial de 100, nós teríamos que percorrer todo o caminho até 0 ... que pode ter um monte de sobrecarga a ele. Da mesma forma, se encontramos uma palavra obscura para procurar no dicionário, isso pode levar olhando para cima outras palavras e verificação de pistas de contexto até encontrarmos uma conexão que estamos familiarizados. métodos recursiva pode levar um longo tempo para trabalhar seu caminho. No entanto, quando eles são usados ​​corretamente, e compreendida, eles podem fazer o trabalho complicado surpreendentemente simples.

Respondeu 04/05/2010 em 17:04
fonte usuário

votos
1

Um grande número de problemas pode ser pensado em dois tipos de peças:

  1. casos base, que são coisas elementares que você pode resolver por apenas olhando para eles, e
  2. casos recursivo, que constroem um problema maior de pedaços menores (elementares ou não).

Então, o que é uma função recursiva? Bem, isso é onde você tem uma função que é definida em termos de si, direta ou indiretamente. OK, isso soa ridículo até você perceber que é sensato para os problemas do tipo descrito acima:-lo a resolver os casos base direta e lidar com os casos recursiva usando chamadas recursivas para resolver os pequenos pedaços do problema incorporado dentro.

O exemplo verdadeiramente clássico de onde você precisa de recursão (ou algo que cheira muito parecido com ele) é quando você está lidando com uma árvore. As folhas da árvore são o caso base, e os ramos são o caso recursiva. (Na pseudo-C.)

struct Tree {
    int leaf;
    Tree *leftBranch;
    Tree *rightBranch;
};

A maneira mais simples de imprimir este para fora, a fim é usar recursão:

function printTreeInOrder(Tree *tree) {
    if (tree->leftBranch) {
        printTreeInOrder(tree->leftBranch);
    }
    print(tree->leaf);
    if (tree->rightBranch) {
        printTreeInOrder(tree->rightBranch);
    }
}

É absolutamente fácil de ver que isso vai funcionar, já que é cristalina. (O equivalente não-recursiva é bastante mais complexa, requerendo uma estrutura de pilha internamente para gerenciar a lista de coisas para processar.) Bem, assumindo que ninguém fez uma conexão circular claro.

Matematicamente, o truque para mostrar que a recursividade é domesticado é se concentrar em encontrar uma métrica para o tamanho dos argumentos. Para o nosso exemplo árvore, a métrica mais fácil é a profundidade máxima da árvore abaixo do nó atual. As folhas, é zero. Em um ramo com só deixa abaixo dela, é uma, etc. Então você pode simplesmente mostrar que não está estritamente ordenou sequência no tamanho dos argumentos que a função é chamado na fim de processar a árvore; os argumentos para as chamadas recursivas são sempre "menor" no sentido da métrica que o argumento para a chamada geral. Com uma métrica cardeal estritamente decrescente, você está classificado.

Também é possível ter recursão infinita. Isso é confuso e em muitas línguas não vai funcionar porque a pilha explode. (Onde ela não funciona, o motor de linguagem deve ser determinar que a função de alguma forma não retorna e é capaz, portanto, para otimizar afastado a manutenção da pilha de coisas complicadas em geral;. Cauda-recursão é apenas a forma mais trivial de fazer isso .)

Respondeu 04/05/2010 em 16:29
fonte usuário

votos
1

Recursão é a técnica de definição de uma função, um conjunto ou um algoritmo, em termos de si.

Por exemplo

n! = n(n-1)(n-2)(n-3)...........*3*2*1

Agora ele pode ser definido recursivamente como: -

n! = n(n-1)!   for n>=1

Em termos de programação, quando uma função ou método chama-se repetidamente, até que alguma condição específica fica satisfeito, este processo é chamado recursão. Mas deve haver uma condição e função de terminação ou método não deve entrar em um loop infinito.

Respondeu 04/05/2010 em 16:22
fonte usuário

votos
1

Recursividade em computação é uma técnica utilizada para calcular um resultado ou efeito colateral após o regresso normal a partir de uma única função (método, processo ou bloco) invocação.

A função recursiva, por definição, tem de ter a capacidade de invocar a si mesmo, quer directamente ou indirectamente (através de outras funções) dependendo de uma condição de saída ou condições de não serem cumpridos. Se uma condição de saída seja cumprido os invocação retornos particulares para ele do chamador. Isto continua até que a chamada inicial é devolvido a partir de, no momento em que o resultado ou lado efeito desejado estará disponível.

Como exemplo, aqui está uma função para executar o algoritmo Quicksort em Scala ( copiado a partir da entrada Wikipedia para Scala )

def qsort: List[Int] => List[Int] = {
  case Nil => Nil
  case pivot :: tail =>
    val (smaller, rest) = tail.partition(_ < pivot)
    qsort(smaller) ::: pivot :: qsort(rest)
}

Neste caso, a condição de saída é uma lista vazia.

Respondeu 04/05/2010 em 15:14
fonte usuário

votos
1

função de chamar-se ou usar sua própria definição.

Respondeu 04/05/2010 em 14:59
fonte usuário

votos
1

Qualquer algoritmo exibe estrutural recursão em um tipo de dados se basicamente consiste em um switch-declaração com um caso 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 algorith que funciona em uma estrutura de dados.

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

 integer = 0 | succ(integer)

você vê que um algoritmo recursivo estrutural em inteiros se parece com isso

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

a função factorial demasiado bem conhecido é o exemplo mais sobre trivial desta forma.

Respondeu 04/05/2010 em 14:53
fonte usuário

votos
1

hey, desculpe se o meu parecer concorda com alguém, estou apenas tentando explicar a recursividade na planície Inglês.

suponha que você tem três gerentes - Jack, John e Morgan. Jack consegue 2 programadores, John - 3, e Morgan - 5. você vai dar a cada gerente de 300 $ e quer saber o que custaria. A resposta é óbvia - mas o que se 2 de funcionários Morgan-s também são gestores?

Aqui vem a recursividade. você começar a partir do topo da hierarquia. o custo de verão é 0 $. você começa com Jack, Em seguida, verifique se ele tem alguma gerentes como empregados. se você encontrar qualquer um deles são, verifique se eles têm alguma gerentes como empregados e assim por diante. Adicionar 300 $ para o custo de verão cada vez que você encontrar um gerente. quando tiver terminado com Jack, ir para John, seus funcionários e, em seguida, a Morgan.

Você nunca vai saber, quanto ciclos você vai percorrer antes de obter uma resposta, mas você sabe quantos gestores que você tem e quantas Budget você pode gastar.

Recursão é uma árvore, com ramos e folhas, chamados de pais e filhos, respectivamente. Quando você usa um algoritmo de recursão, você mais ou menos conscientemente estão construindo uma árvore a partir dos dados.

Respondeu 04/05/2010 em 13:50
fonte usuário

votos
1

Na planície Inglês, recursão significa repetir someting novamente e novamente.

Na programação um exemplo é de chamar a função dentro de si.

Olhe no exemplo de cálculo fatorial de um número a seguir:

public int fact(int n)
{
    if (n==0) return 1;
    else return n*fact(n-1)
}
Respondeu 04/05/2010 em 13:48
fonte usuário

votos
1

Recursividade é o processo em que uma chamada de método iself para ser capaz de executar uma determinada tarefa. Ele reduz redundency de código. A maioria das funções ou métodos recurssive deve ter um condifiton para quebrar o recussive chamar isto é impedi-lo de que se autodenomina se uma condição é satisfeita - isto impede a criação de um loop infinito. Nem todas as funções são adequados para ser usado de forma recursiva.

Respondeu 04/05/2010 em 13:42
fonte usuário

votos
1

é uma maneira de fazer as coisas, uma e outra indefinidamente tal que cada opção é usada.

por exemplo, se você quisesse obter todos os links em uma página html que você vai querer ter recursions porque quando você começa todos os links na página 1 você vai querer ter todos os links em cada um dos links encontrados na primeira página. em seguida, para cada link para uma newpage você vai querer esses laços e assim por diante ... em outras palavras, é uma função que se chama de dentro si.

quando você fizer isso você precisa encontrar uma maneira de saber quando parar ou então você vai estar em um loop infinito para que você adicionar um parâmetro inteiro para a função de controlar o número de ciclos.

no c # você terá algo parecido com isto:

private void findlinks(string URL, int reccursiveCycleNumb)    {
   if (reccursiveCycleNumb == 0)
        {
            return;
        }

        //recursive action here
        foreach (LinkItem i in LinkFinder.Find(URL))
        {
            //see what links are being caught...
            lblResults.Text += i.Href + "<BR>";

            findlinks(i.Href, reccursiveCycleNumb - 1);
        }

        reccursiveCycleNumb -= reccursiveCycleNumb;
}
Respondeu 04/05/2010 em 13:02
fonte usuário

votos
1

"Se eu tiver um martelo, fazem tudo parecer com um prego."

Recursão é uma estratégia de resolução de problemas para enormes problemas, onde a cada passo apenas, "virar 2 pequenas coisas em uma coisa maior", cada vez com o mesmo martelo.

Exemplo

Suponha que sua mesa é coberta com uma bagunça desorganizada de 1024 papéis. Como você faz um puro pilha, limpo de papéis da confusão, usando recursão?

  1. Divide: Espalhe todas as folhas para fora, para que você tenha apenas uma folha em cada "pilha".
  2. Conquistar:
    1. Vá ao redor, colocando cada folha em cima de uma outra folha. Agora você tem pilhas de 2.
    2. Vá ao redor, colocando cada 2-stack em cima do outro 2-stack. Agora você tem pilhas de 4.
    3. Vá ao redor, colocando cada 4-stack em cima do outro 4-stack. Agora você tem pilhas de 8.
    4. ... e em ...
    5. Você agora tem uma enorme pilha de 1024 folhas!

Observe que este é bastante intuitivo, além de contar tudo (o que não é estritamente necessário). Você não pode ir todo o caminho até a pilhas 1 folha, na realidade, mas você poderia e ainda iria funcionar. A parte importante é o martelo: Com seus braços, você pode sempre colocar uma pilha em cima do outro para fazer uma pilha maior, e não importa (dentro da razão) como grande quer pilha é.

Respondeu 04/05/2010 em 12:54
fonte usuário

votos
1

Recursividade como se aplica a programação é basicamente chamar uma função de dentro de sua própria definição (dentro de si), com parâmetros diferentes, de modo a realizar uma tarefa.

Respondeu 04/05/2010 em 12:25
fonte usuário

votos
1

Você quer usá-lo sempre que você tem uma estrutura de árvore. É muito útil na leitura XML.

Respondeu 21/08/2008 em 14:18
fonte usuário

votos
1

Mario, eu não entendo por que você usou recursão para esse exemplo .. Por que não simplesmente loop através de cada entrada? Algo assim:

String ArrangeString(TStringList* items, String separator)
{
    String result = items->Strings[0];

    for (int position=1; position < items->count; position++) {
        result += separator + items->Strings[position];
    }

    return result;
}

O método acima seria mais rápido e é mais simples. Não há necessidade de usar a recursividade no lugar de um loop simples. Eu acho que esses tipos de exemplos É por isso que a recursividade começa uma batida má. Mesmo o exemplo função fatorial canônica é melhor implementado com um loop.

Respondeu 06/08/2008 em 04:19
fonte usuário

votos
0

Na verdade, a melhor solução recursiva para fatorial deve ser:

int factorial_accumulate(int n, int accum) {
    return (n < 2 ? accum : factorial_accumulate(n - 1, n * accum));
}

int factorial(int n) {
    return factorial_accumulate(n, 1);
}

Porque esta versão é Cauda recursiva

Respondeu 21/08/2008 em 14:39
fonte usuário

votos
0

Eu uso a recursividade. O que isso tem a ver com ter um grau CS ... (o que eu não faço, por sinal)

Os usos mais comuns que eu encontrei:

  1. sitemaps - recurse através de sistema de arquivos a partir de raiz do documento
  2. aranhas - rastejando através de um site para encontrar o endereço de e-mail, links, etc.
  3. ?
Respondeu 06/08/2008 em 04:13
fonte usuário

votos
0

Eu criei uma função recursiva para concatenar uma lista de strings com um separador entre eles. Eu usá-lo principalmente para criar expressões SQL, passando uma lista de campos como os ' itens ' e uma ' vírgula + espaço ' como separador. Aqui está a função (Ele usa alguns tipos de dados nativa Borland Builder, mas pode ser adaptado para caber qualquer outro ambiente):

String ArrangeString(TStringList* items, int position, String separator)
{
  String result;

  result = items->Strings[position];

  if (position <= items->Count)
    result += separator + ArrangeString(items, position + 1, separator);

  return result;
}

Eu chamo-lhe assim:

String columnsList;
columnsList = ArrangeString(columns, 0, ", ");

Imagine que você tem uma matriz chamada ' campos ' com esses dados dentro dele: ' albumName ', ' releasedate ', ' labelId '. Em seguida, você chamar a função:

ArrangeString(fields, 0, ", ");

À medida que a função começa a trabalhar, o 'variável resultado ' recebe o valor da posição 0 da matriz, o que é ' albumName '.

Em seguida, ele verifica se a posição que está lidando com é o último. Como não é, em seguida, ele concatena o resultado com o separador e o resultado de uma função, que, oh Deus, é esta mesma função. Mas desta vez, verificá-la, ela chamar-se adicionando 1 para a posição.

ArrangeString(fields, 1, ", ");

Ele continua a repetir, criando uma pilha LIFO, até atingir um ponto em que a posição a ser tratado é o último, então a função retorna somente o item em que posição na lista, não concatenar mais. Em seguida, a pilha é concatenado para trás.

Consegui? Se não o fizer, tenho outra maneira de explicá-lo. : O)

Respondeu 06/08/2008 em 04:00
fonte usuário

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more