Recursão em C

Uma função pode chamar a si mesma. Esse processo é chamado recursão em C. A recursão pode ser direta ou indireta.

Ela é direta quando a função chama a si mesma, na recursão indireta, uma função chama outra função, que por sua vez chama a primeira função.

Alguns problemas são solucionados com mais facilidade com o uso de recursão.

Geralmente são problemas nos quais fazemos um cálculo com os dados, e depois fazemos novamente o mesmo cálculo com o resultado.

A recursão pode ter um final feliz, quando a cadeia de recursão chega a um fim e temos um resultado. Ou pode ter um final infeliz, quando a cadeia recursiva não tem fim e acaba travando o programa.

É importante entender que quando uma função chama a si mesma, uma nova cópia da função passa a ser executada.

As variáveis locais da segunda cópia são independentes das variáveis locais da primeira cópia, e não podem afetar umas às outras diretamente.

Um exemplo clássico de uso de recursão é a sequência matemática chamada série de Fibonacci. Na série de Fibonacci, cada número, a partir do terceiro, é igual à soma dos dois números anteriores. Eis a série de Fibonacci:

1, 1, 2, 3, 5, 8, 13, 21, 34…

Geralmente, o que se deseja é determinar qual o n-ésimo número da série. Para solucionar o problema, precisamos examinar com cuidado a série de Fibonacci.

Os primeiros dois elementos são iguais a 1. Depois disso, cada elemento subsequente é igual à soma dos dois anteriores.

Por exemplo, o sétimo número é igual à soma do sexto com o quinto. Ou, dito de um modo genérico, o n-ésimo número é igual à soma do elemento n – 1 com o elemento n – 2, desde que n > 2.

Para evitar desastres, uma função recursiva precisa ter uma condição de parada. Alguma coisa precisa acontecer para fazer com que o programa encerre a cadeia recursiva, senão ela se tornará infinita. Na série de Fibonacci, essa condição é n < 3.

Portanto, o algoritmo usado será:

a) Solicitar do usuário a posição desejada na série;

b) Chamar a função Fibonacci, fibo(), usando como argumento essa posição, passando o valor digitado pelo usuário.

c) A função fibo() examina o argumento n. Se n < 3, a função retorna 1; caso contrário, a função fibo() chama a si mesma recursivamente, passando como argumento n – 2, e depois chama a si mesma novamente, passando como argumento n – 1, e retorna a soma.

Assim, se chamarmos fibo(1), ela retornará 1. Se chamarmos fibo(2), ela retornará 1. Se chamarmos fibo(3), ela retornará a soma das chamadas fibo(2) + fibo(1). Como fibo(2) retorna 1 e fibo(1) retorna 1, fibo(3) retornará 2.

Se chamarmos fibo(4), ela retornará a soma das chamadas fibo(3) + fibo(2). Já mostramos que fibo(3) retorna 2, chamando fibo(2) + fibo(1). Mostramos também que fibo(2) retorna 1, de modo que fibo(4) somará esses dois números e retornará 3, que é o quarto elemento da série.

O exemplo abaixo ilustra o uso desse algoritmo:

// Utiliza a série de Fibonacci para demonstrar o uso de uma função recursiva
#include <iostream.h>

// Protótipo
int fibo(int i);

// Calcula o valor do i-ésimo elemento da série de Fibonacci
int main() {
	
   int n, resp;
   cout << "Digite um numero: + Enter: ";
   cin >> n;
   resp = fibo(n);
   cout << "\nElemento "
   << n
   << " na serie Fibonacci = "
   << resp;
   return 0;
} // Fim de main()
    
// Definição
int fibo(int i) {

   // Calcula o valor do i-ésimo elemento da série de Fibonacci	
   cout << "\nProcessando fibo("
   << i
   << ")...";
   if(i < 3) {

      cout << "Retornando 1...\n";
      return 1;
   } else { // Fim de if
		
      cout << "Chamando fibo("
      << i - 2
      << ") e fibo("
      << i - 1
      << ").\n";
      return(fibo(i - 2) + fibo(i - 1));
    } // Fim de else
 } // Fim de fibo(int)

Ponteiros para objetos em C

Dúvidas ou sugestões? Deixem nos comentários! Para mais dicas, acesse o nosso canal no YouTube:
https://youtube.com/criandobits

Tags: recursao