recursion - usar - recursão indireta




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

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. 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).


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