Funções recursivas. Recursividade

Explicamos o que é uma função recursiva e como implementar recursividade ou fazer funções recursivas em uma linguagem de programação.

Por Miguel Angel Alvarez - Tradução de Celeste Veiga


Publicado em: 03/7/12
Valorize este artigo:
Dentro do manual de iniciação à programação que vimos publicando em CriarWeb.com, vamos ver uma das primeiras coisas ensinadas na criação de algoritmos: a recursividade.

Como definição geral, podemos dizer que uma função recursiva é aquela que se chama a ela mesma para se resolver. Dito de outra maneira, uma função recursiva se resolve com uma chamada a ela mesma, mudando o valor de um parâmetro na chamada à função. Através das sucessivas chamadas recursivas à função vão sendo obtidos valores que, computados, servem para obter o valor da função chamada originalmente.

O processo de chamadas recursivas sempre tem que acabar em uma chamada à função que se resolve de maneira direta, sem necessidade de invocar de novo a função. Isto será sempre necessário, para que chegue um momento que se cortem as chamadas reiterativas à função e não se entre em um looping infinito de invocações.

Talvez na teoria custe mais ver o que é uma função recursiva que na prática. Um exemplo típico de recursividade seria a função fatorial. O fatorial é uma função matemática que se resolve multiplicando esse número por todos os números naturais que há entre ele e 1.

Por exemplo, fatorial de 4 é igual a 4 * 3 * 2 * 1. Se observarmos, para o exemplo de fatorial de 4 (fatorial se expressa matematicamente com um signo de exclamação, como 4!), se pode resolver como 4 * 3! (4 * fatorial de 3). Ou seja, podemos calcular o fatorial de um número multiplicando esse número por fatorial desse número menos 1.

n! = n * (n-1)!

No caso da função fatorial, temos o caso básico que fatorial de 1 é igual a 1. De modo que poderemos utilizá-lo como ponto de ruptura das chamadas recursivas.

Assim, vamos realizar a codificação da função recursiva fatorial. Primeiro vejamos um pseudocódigo:

funcao fatorial(n)
   se n=1 entao
      fatorial = 1
   senao
      fatorial = n * fatorial(n-1)
fim funcao

Agora vejamos como se implementaria esta função com a linguagem de programação Javascript:

function factorial(n){
   if(n==1)
      return 1
   else
      return n * factorial(n-1)
}

Como se pode ver, a recursividade não representa nenhuma dificuldade e de fato é uma ferramenta muito útil para programação de algoritmos. Em Criar web.com publicamos em diversos lugares funções que trabalham de forma recursiva. Entendo que em principio pode resultar difícil de entender ou de saber quando utilizar, mas quando dominemos o conceito veremos que é uma maneira excelente de resolver problemas com qualquer linguagem de programação.

Há muitos algoritmos que só se resolvem com recursividade, o pelo menos cuja resolução mais direta e elegante está baseada em realizar funções recursivas, que se chamem a elas mesmas para obter o resultado final. Por exemplo, o percurso de diversas estruturas de dados, como as de tipo árvore, sempre se costumam realizar de maneira recursiva, para poder ter certeza de que passamos por todas os ramos da árvore.

Referencia: Dou alguns endereços de artigos de CriarWeb.com que resolvam problemas criando funções recursivas:






Usuários :    login / registro

Manuais relacionados
Categorias relacionadas
O autor

Home | Sobre nós | Copyright | Anuncie | Entrar em contato