O que é recursão na programação e como usá-la?

Shutterstock / Olga Donchuk

A recursão é uma parte importante da programação funcional que pode ajudar a resolver problemas complexos com soluções elegantes. No entanto, é importante entender os prós e os contras para que isso possa ser feito corretamente.

RELACIONADO: O que é recursão na programação e como usá-la?

O que é recursão?

A resposta curta é que a recursão é basicamente sempre que uma função chama a si mesma, geralmente com uma entrada diferente passada para a função filha. Ele chama a si mesmo continuamente até que uma condição de saída seja alcançada e, em seguida, passa os resultados de volta para a pilha de chamadas, potencialmente modificando-os também no caminho.

A resposta longa é que a recursão pode ajudar a resolver problemas complicados, dividindo-os em subconjuntos menores do problema principal. Freqüentemente, você terá estruturas de dados contendo dados aninhados. Dividir isso em quantidades menores de dados tornará isso mais fácil de processar.

Por exemplo, digamos que cada folha da árvore tenha um valor associado a ela e desejamos encontrar a soma de todos os valores. Poderíamos fazer isso com uma função como a seguinte, que percorre a árvore folha por folha, inspecionando todos os filhos e calculando o total.

int CountAllLeaves & # 40; Leaf currentLeaf & # 41; & # 123; // Começa com o valor atualint Total = currentLeaf. value; // Adiciona quaisquer filhos ao valor, if anyforeach & # 40; Leaf childLeaf in currentLeaf. children & # 41; & # 123; Total = Total + CountAllLeaves & # 40; childLeaf & # 41 ;; & # 125; return Total; & # 125;

Isso funciona porque CountAllLeaves não se importa com qual Leaf você usará. Ele chama a si mesmo repetidamente até atingir a folha final da árvore, que não tem filhos. Por isso, ele simplesmente retorna seu próprio valor. Esse valor é passado para a folha pai, que adiciona o valor filho ao seu próprio e, em seguida, repete para todos os irmãos que a folha filha tem. No final, o resultado final da função será a soma total de todas as folhas da árvore.

Em algum ponto, você deve chegar ao caso de interrupção, que é a parte do problema para a qual você sabe a resposta, sem fazer mais chamadas recursivas. Caso contrário, a função entraria em loop para sempre, fazendo com que o programa travasse. Nesse caso, o caso de parada é quando a função atinge uma folha que não tem filhos.

Não precisa ser sobre estruturas de dados aninhadas como árvores. Você pode escrever funções recursivas em torno de qualquer tipo de problema. Por exemplo, calcular o fatorial de um número envolve multiplicá-lo por cada número menor que ele. Você pode fazer isso facilmente com recursão:

int Fatorial & # 40; int n & # 41; & # 123; if & # 40; n < = 1 & # 41; return1;   return n * Fatorial & # 40; n-1 & # 41 ;; & # 125;

Neste exemplo, o caso de interrupção é quando n atinge 1, onde finalmente retorna um valor e a pilha de chamadas pode ser reduzida.

Vejamos um exemplo do mundo real. Neste trecho de código, há uma classe Container que contém vários elementos de IU anexados a ela, bem como vários containers filho com seus próprios elementos. Deve ser “ renderizado ” para uma lista simples de elementos que podem ser mostrados na tela.

Esta é basicamente outra estrutura de dados em árvore, então a abordagem é semelhante. Exceto, neste caso, a variável total é uma lista, que obtém as listas de elementos de cada contêiner anexado a ela.

A mágica de fazer isso usando recursão é que ela preserva a ordem Z dos elementos. Os elementos desenhados após outros elementos vão para o topo, de modo que o contêiner filho mais novo sempre será exibido no topo. Nesse cenário, também achei útil exibir elementos de sobreposição, que são adicionados depois que os outros elementos e os filhos terminam a renderização.

Os perigos da recursão

Então, quando você deve usar recursão em seu código? A resposta é que você provavelmente deve evitá-lo na maioria das situações, especialmente quando uma solução iterativa usando um loop simples fará o trabalho.

Cada vez que você chama uma função, seu programa aloca recursos para essa função. Todas as variáveis ​​locais e informações vão para a pilha, que é uma estrutura de dados LIFO (Last-In, First-Out). Isso significa que a última chamada de função é sempre a primeira a ser removida, como um balde de onde você sempre remove o elemento superior.

O problema com a recursão é que ela pode usar uma chamada de função aninhada para cada elemento sendo processado. Isso resulta em muito mais sobrecarga, pois cada chamada de função precisa de seu próprio conjunto de variáveis ​​e parâmetros locais. Levará mais tempo de processamento em comparação com uma abordagem baseada em loop.

Os loops não têm esse problema. Após cada iteração de loop, a pilha terá o elemento superior removido. Ele poderia processar um bilhão de elementos usando a mesma pilha.

Se você usar muitos recursos com chamadas de função recursivas, isso pode resultar em estouro de pilha, onde o programa pode travar apenas com base em muitas chamadas aninhadas. Isso pode acontecer com conjuntos de dados particularmente grandes ou com algoritmos deficientes, como recursão binária ou exponencial, que se autodenominam várias vezes por chamada de função.

Use a recursão com moderação

A recursão é uma coisa boa para certos problemas, mas basicamente não existem soluções recursivas para problemas que também não podem ser resolvidos usando loops (exceto para recursão aninhada como a função de Ackerman). Mesmo estruturas de dados de árvore complicadas podem ser percorridas usando loops e pilhas. Se você precisa lidar com grandes quantidades de dados ou se preocupa muito com o desempenho, é melhor usar uma solução iterativa.

O outro problema com a recursão é que ela pode levar a um código difícil de ser entendido por outras pessoas, já que normalmente é necessário um pouco de esforço antes de alguém entendê-lo. Embora muitas vezes pareça ser o mais “ elegante ” solução, seu trabalho como programador não é se exibir, mas sim escrever um código funcional e legível.

Em qualquer caso, você vai querer pensar se o problema em questão seria melhor ou não usando um loop. A recursão deve ser seu último recurso para problemas que seriam muito mais complicados sem ela. Na verdade, em todas as minhas 40.000 linhas de código-fonte, só tive um exemplo de recursão para este artigo.

E, depois de dar uma segunda olhada nele, realmente percebi um problema. Embora tenha funcionado bem, foi escrito de forma preguiçosa e óbvia e, como tal, está usando muito mais memória do que o necessário. Isso não é realmente um problema com as pequenas estruturas de dados com as quais está lidando, mas estava criando uma nova List < CuiElement > () para cada chamada da função e adicionando os resultados dos filhos abaixo dela. Isso significava que, se recebesse um contêiner com filhos profundamente aninhados, ele armazenaria os mesmos dados indefinidamente sem motivo.

A solução neste caso foi passar à função recursiva uma referência a uma lista externa e adicionar todos os elementos a ela diretamente. Isso também envolveu a mudança da função Render () em uma função que manipulava a configuração de nível superior para a função de compilação recursiva.

Isso realiza exatamente a mesma solução de adicionar cada elemento na ordem adequada, mas corrige o problema de uso de memória que aumenta exponencialmente a cada chamada.

Ainda assim, estou satisfeito com esta função, pois é bastante concisa e realiza o trabalho facilmente. Se eu fosse converter isso em uma solução usando um loop, seria muito mais complicado e faria exatamente a mesma coisa. Você precisará pesar os prós e os contras de usar uma solução recursiva e só usá-los onde não estiver esperando um uso sério de recursos. Nesse caso, não espero chamar esta função com contêineres aninhados com centenas de elementos de profundidade, portanto, usar recursão aqui é bom.

Para obter mais informações sobre este tópico, consulte nosso guia de recursão.