Recursividade

Uma função recursiva é uma função que se refere a si própria. A ideia consiste em utilizar a própria função que estamos a definir na sua definição.

Em todas as funções recursivas existe:

• Um passo básico (ou mais) cujo resultado é imediatamente conhecido.

• Um passo recursivo em que se tenta resolver um sub-problema do problema inicial.  

Geralmente, uma função recursiva só funciona se tiver uma expressão condicional, mas não é obrigatório que assim seja. A execução de uma função recursiva consiste em ir resolvendo subproblemas sucessivamente mais simples até se atingir o caso mais simples de todos, cujo resultado é imediato. Desta forma, o padrão mais comum para escrever uma função recursiva é: 

• Começar por testar os casos mais simples.

• Fazer chamada (ou chamadas) recursivas com subproblemas cada vez mais próximos dos casos mais simples.

 Os dois problemas mais utilizados para ensinar recursividade são: o fatorial e o fibonacci.

Abaixo estão implementados os dois problemas em Python e em C++.

Código em Python

def fatorial(n):
  if n == 0:
      return 1
  else:
      return n * fatorial(n-1)

def fibonacci(n):
    if n == 0 or n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)
    
print fatorial(5)
print fibonacci(5)

Código em C++

#include <iostream>

using namespace std;

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

int fibonacci(int n)
{
  if (n == 0 || n == 1)
    return 1;
  else
  {
     return fibonacci(n-1) + fibonacci(n-2);
  }
}

int main() 
{
   cout << fatorial(5) << endl;
   cout << fibonacci(5) << endl;
   return 0;
}

Como podemos observar, são funções que chamam a si mesmas, até chegar ao entendimento do funcionamento da recursão você pode ter muitas dores de cabeça.