CriandoBits
Identifique-se Entrar Esqueceu a senha? Esqueci minha senha

C/C++ - Recursão

Por Benedito Silva Júnior - publicado em 20/06/2016


Uma função pode chamar a si mesma. Esse processo é chamado recursão. 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:

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; } // Fim de if else { cout << "Chamando fibo(" << i - 2 << ") e fibo(" << i - 1 << ").\n"; return(fibo(i - 2) + fibo(i - 1)); } // Fim de else } // Fim de fibo(int)


 
Voltar a pagina anteriorVoltarSubir ao topo da páginaTopo