recursion - usar - recursão indireta




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

  1. Uma função que se chama
  2. Quando uma função pode ser (facilmente) decomposta em uma operação simples mais a mesma função em uma parte menor do problema. Antes, devo dizer 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 da chamada de função tende a ser alta porque as funções recursivas tendem a ser pequenas, veja acima) e podem sofrer de alguns problemas (a pilha excede alguém?). 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. Note-se que alguns idiomas favorecem soluções recursivas e as otimizam muito mais (LISP vem à mente).

Um dos tópicos que parece surgir regularmente nas listas de discussão e discussões on-line é 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 estão 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?

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 passagem em árvore, como pré-encomenda e pós-encomenda, podem ser iterativas e recursivas. Mas geralmente usamos recursivos devido à sua simplicidade.


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


A recursão está resolvendo um problema com uma função que se chama. Um bom exemplo disso é uma função fatorial. Fatorial é um problema de matemática em que fatorial de 5, por exemplo, é 5 * 4 * 3 * 2 * 1. Essa função resolve isso em C # para números inteiros positivos (não testados - pode haver um erro).

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

    return n * Factorial(n - 1);
}

Aqui está um exemplo simples: quantos elementos em um conjunto. (existem maneiras melhores de contar as 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: [xxx]. vamos contar quantos itens existem.

  1. o conjunto é [xxx] que não está vazio, então aplicamos a regra 2. o número de itens é um mais o número de itens em [xx] (ou seja, removemos um item).
  2. como o conjunto é [xx], 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 [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:

  • com base, o caso simples que indica o que acontece quando você "esgotou" todos os seus dados. Isso geralmente é uma variação de "se você não tiver dados para processar, sua resposta será X"
  • a regra recursiva, que informa o que acontece se você ainda tiver dados. Geralmente, esse é um tipo de regra que diz "faça algo para diminuir o conjunto de dados e aplique novamente as regras ao conjunto de dados menor".

Se traduzirmos o código acima em pseudocódigo, obteremos:

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

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


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

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


Em inglês simples, recursão significa repetir algumas vezes.

Na programação, um exemplo é chamar a função em si.

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

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

Em inglês simples: suponha que você possa fazer 3 coisas:

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

Você tem muitas maçãs à sua frente em uma mesa e deseja 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é você terminar é chamado de recursão.

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


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

Também gosto da discussão de Steve McConnells sobre recursão no Code Complete, onde ele critica os exemplos usados ​​nos 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 de ciência da computação é que eles apresentam exemplos tolos de recursão. Os exemplos típicos são computar um fatorial ou computar 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 recursão para calcular um fatorial, eu contrataria outra pessoa.

Eu pensei que este era um ponto muito interessante a ser levantado e pode ser uma razão pela qual a recursão é muitas vezes incompreendida.

Edição: Esta não foi uma escavação na resposta de Dav - eu não tinha visto essa resposta quando publiquei este


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.

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

struct Node {
    Node* next;
};

E você deseja descobrir quanto tempo 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);
    }
}

(Isso também pode ser feito com um loop for, mas é útil como ilustração do conceito)


Para recorrer a um problema resolvido: não faça nada, está feito.
Para se retribuir em um problema em aberto: execute o próximo passo e repasse o restante.


Recursão é o processo em que uma chamada de método é capaz de executar uma determinada tarefa. Reduz a redundância de código. A maioria das funções ou métodos recursivos deve ter uma condição para interromper a chamada recussiva, ou seja, interromper a chamada própria se uma condição for atendida - isso impede a criação de um loop infinito. Nem todas as funções são adequadas para serem usadas recursivamente.


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

Considere acrônimos recursivos como um exemplo simples:

  • GNU significa Not Unix do GNU
  • PHP significa PHP: pré-processador de hipertexto
  • YAML significa YAML Ain't Markup Language
  • WINE significa Wine Is Not a Emulator
  • VISA significa Visa International Service Association

Mais exemplos na Wikipedia


Sempre que uma função se chama, criando um loop, isso é recursão. Como em qualquer coisa, existem bons usos e maus usos para 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 inútil, quase inútil, porque pode ser facilmente substituído por uma iteração mais eficiente. Afinal, a recursão sofre de sobrecarga de chamada de função, que no exemplo acima pode ser substancial em comparação com a operação dentro da própria função.

Portanto, todo o motivo para fazer recursão em vez de iteração deve ser aproveitar a 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, é uma maneira de realizar branching . Um exemplo clássico é o triângulo de Sierpinski .

Você pode desenhar um desses de maneira 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 precisará de muito mais código para realizar.

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

Conclusão

Em termos práticos, a recursão faz mais sentido sempre que você precisar de ramificações iterativas.


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


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 puro efeito infinito que eles produzem. Cada reflexão é uma instância de um espelho, que está contida em outra instância de um espelho, etc. O espelho que contém um reflexo de si mesmo é recursão.

Uma á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ó. As funções para trabalhar em uma árvore de pesquisa binária também são recursivas.


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


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


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

A recursão é uma estratégia de solução de problemas para grandes problemas, onde a cada passo apenas "transforma duas pequenas coisas em uma coisa maior", cada vez com o mesmo martelo.

Exemplo

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

  1. Dividir: espalhe todas as folhas, para que você tenha apenas uma folha em cada "pilha".
  2. Conquistar:
    1. Vá ao redor, colocando cada folha em cima de outra folha. Agora você tem pilhas de 2.
    2. Vá ao redor, colocando cada pilha 2 em cima de outra pilha 2. Agora você tem pilhas de 4.
    3. Vá ao redor, colocando cada pilha de 4 em cima de outra pilha de 4. Agora você tem pilhas de 8.
    4. ... e assim por diante ...
    5. Agora você tem uma enorme pilha de 1024 folhas!

Observe que isso é bastante intuitivo, além de contar tudo (o que não é estritamente necessário). Na verdade, talvez você não vá até as pilhas de 1 folha, 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 criar uma pilha maior, e não importa (dentro da razão) qual o tamanho de uma pilha.





computer-science