O que é recursão e como você a usa?

gurinho

A recursão é um conceito de programação divertido, mas pode ser um pouco complicado de aprender. Recursão significa simplesmente algo que se repete. Se você quiser ver um exemplo atrevido de recursão, tente pesquisar por recursão no Google. Você encontrará um ovo de Páscoa em que as sugestões de resultados da pesquisa são recursivas. Se, por outro lado, você gostaria de aprender como codificar uma função recursiva, continue lendo!

O que é uma função recursiva?

Uma função recursiva é uma função que chama a si mesma. Você essencialmente cria um loop com uma função. Como você pode imaginar, essas funções podem ser complicadas de escrever. Você não quer que seu código seja executado para sempre.

Semelhante a um loop, uma função recursiva será controlada por uma condição. Assim que a condição for atendida, a função para de chamar a si mesma, o que interrompe o loop. É assim que você pode criar uma função que chama a si mesma sem ser executada para sempre.

Embora uma função recursiva atue como um loop, ela é executada pelo computador de forma diferente. Portanto, alguns algoritmos são mais eficientes em um loop e outros se beneficiam de uma função recursiva. Mas antes de olharmos como usar uma função recursiva, você precisa saber como escrever uma.

Como escrever uma função recursiva

Todas as funções recursivas têm a mesma estrutura básica:

 FUNCTION name
 IF condition THEN
 RETURN result
 ELSE
 CALL FUNCTION name
 END FUNCTION

O exemplo acima foi escrito em pseudo-código. Ele descreve a estrutura da função, que pode ser aplicada a qualquer idioma. Para simplificar, neste artigo, vamos nos concentrar em Python.

A primeira coisa a observar sobre uma função recursiva é que quando a condição é atendida, a função sai da recursão. Isso significa que quando você escreve uma função recursiva, a primeira coisa que você vai querer determinar é quando parar a recursão.

Se a condição não for atendida, a função chamará a si mesma. Portanto, se você quiser enviar informações para o próximo loop, terá que enviá-las como um argumento em sua função. Isso pode dar às funções recursivas muito mais poder.

Relacionado: O que é uma função na programação?

Exemplo de função recursiva em Python

Será muito mais fácil entender como funciona a recursão quando você a vir em ação. Para demonstrar isso, vamos escrever uma função recursiva que retorna o fatorial de um número.

Os fatoriais retornam o produto de um número e de todos os inteiros antes dele. Por exemplo, o fatorial de 5 é 5 x 4 x 3 x 2 x 1 ou 120.

 def factorialFunction(numberToMultiply):
 if numberToMultiply == 1 :
 return 1
 else :
 return numberToMultiply * factorialFunction(numberToMultiply - 1)

 result = factorialFunction(3)
 print(result)
 //Outputs: 6

O programa acima fornecerá o resultado 6, que é o fatorial do número 3. Isso pode ser um pouco confuso no início. Será útil se executarmos o programa passo a passo.

  1. Quando a função é chamada, numberToMultiply é igual a 3.
  2. A condição não é atendida, então vamos para a condição else .
  3. Nossa função retorna 3 *, mas é pausada. Ele deve chamar a si mesmo para determinar o restante do valor que está retornando.
  4. Quando a função é chamada desta vez, o valor de numberToMultiply é igual a 2.
  5. A condição não é atendida, então vamos para a condição else.
  6. Nossa função retorna 2 *, mas é então pausada. Ele deve chamar a si mesmo para determinar o restante do valor que está retornando.
  7. A função é chamada novamente. Desta vez, o valor de numberToMultiply é igual a 1.
  8. Nossa condição if for atendida. A função retorna 1.
  9. A função da etapa 6 agora pode retornar 2 * 1 para a função da etapa 3.
  10. A função na etapa três agora pode retornar 3 * 2 * 1, que é 6.

A recursão é um conceito complicado. Pode ser útil pensar nisso como o empilhamento de uma função em cima de outra. Depois que uma função é finalmente resolvida, ela pode enviar as informações de volta para a pilha, até que todas as funções tenham sua resposta.

Isso é basicamente o que o seu computador faz. Quando você chama a função, ela é mantida na memória até que seja retornada. Isso significa que as funções recursivas podem usar muito mais memória do que um loop.

Portanto, pode não ser eficiente escrever loops como funções recursivas, mas é uma ótima maneira de praticar sua construção. Você deve ser capaz de codificar loops como funções recursivas com resultados semelhantes.

Um exemplo de como converter um loop em uma função recursiva

 print("Enter an even number:")
 i = int(input())
 while (i % 2) != 0 :
 print("That number is not even. Please enter a new number:")
 i = int(input())

Este loop também pode ser escrito recursivamente como:

 def recursiveFunction(number) :
 if (number % 2) == 0 :
 return number
 else:
 print("That number is not even. Please enter a new number:")
 recursiveFunction(int(input()))

 print("Enter and even number:")
 i = recursiveFunction(int(input()))

A primeira etapa é determinar quando você deseja que a função pare. Nesse caso, queremos que ele pare assim que um número par for inserido. Em nosso exemplo, number rastreia a entrada do usuário. Se eles inserirem um número par, retornamos o número. Caso contrário, continuaremos a pedir um novo número.

Para configurar o loop, chamamos nossa função novamente. Mas, desta vez, o número que passamos para a próxima função é o novo número inserido pelo usuário. A próxima chamada de função verificará o número.

Esta é uma função muito ruim! Sim, está verificando se o número é par, como nosso loop, mas não é eficiente. Cada vez que o usuário insere um número ímpar, a função é mantida na memória e uma nova função é chamada. Se você fizer isso várias vezes, ficará sem memória!

Relacionado: Exemplos básicos de Python que o ajudarão a aprender rápido

Um exemplo do mundo real de uma função recursiva

Os exemplos acima são bons exemplos de quando não usar recursão. Então, onde a recursão é usada? Um bom exemplo de quando você deseja usar a recursão é pesquisar uma árvore binária.

Quando os dados são estruturados em uma árvore binária, você tem que percorrer vários caminhos para pesquisar os dados. Em cada ponto da árvore, você deve decidir se deseja continuar a pesquisar à direita ou à esquerda. Você pode salvar qual parte da árvore visitou em uma variável, mas uma função recursiva pode rastrear naturalmente essa informação.

Imagine que estamos procurando o número seis na árvore acima. Poderíamos fazer uma função recursiva que pesquisa a árvore da esquerda para a direita. O algoritmo seria mais ou menos assim:

 FUNCTION searchTree(branchToSearch)
 IF find 6 OR end of tree THEN
 RETURN result
 ELSE
 PROCESS branch
 CALL FUNCTION searchTree(left)
 CALL FUNCTION searchTree(right)
 END FUNCTION

Neste exemplo de pseudocódigo, o algoritmo pesquisaria primeiro o lado esquerdo da árvore. Cada vez que ele visita um novo número, a função é pausada e mantida na memória. Isso nos permite rastrear onde estivemos.

O algoritmo sempre pesquisará o lado esquerdo o mais longe que puder primeiro. assim que chegar ao final da árvore, o searchTree (à esquerda) será concluído e verificará o lado direito. Uma vez que ambos os lados são verificados, a busca retorna um galho e continua verificando o lado direito.

Se os algoritmos pesquisassem a árvore inteira, eles o fariam na ordem:

2, 7, 2, 6, 5, 11, 5, 9 e 4

Veja se você pode acompanhar usando o pseudocódigo acima.

Revisão de recursão

A recursão é um tópico avançado. Levará algum tempo para entender e ainda mais para ficar bom em codificá-lo. Será útil se você percorrer as funções recursivas passo a passo. Pode até ajudar empilhar cartões de índice ou post-its à medida que você executa uma função ao aprender a representar cada chamada de função.

Ao escrever uma função recursiva, comece decidindo como deseja sair da função. Em seguida, determine como configurar seu loop. Identifique quais informações devem ser enviadas para a próxima chamada de função e quais devem ser retornadas.

A melhor maneira de aprender a recursão é praticá-la e aprender com seus erros. Observe alguns de seus códigos antigos e desafie-se a reescrever loops como funções recursivas. Provavelmente não tornará seu código mais eficiente, mas será uma boa prática.