Funções Recursivas em C/C++

Prévia do material em texto

Laboratório de Programação de 
Computadores II
Pontifícia Universidade Católica de Minas Gerais
Computadores II
Aula 4
Prof. Lucas Schmidt
Linguagem C/C++
Documentos auxiliares:
Manual C-C++
Curso Linguagem C-C++ UFMGCurso Linguagem C-C++ UFMG
Disponível no site para download:
https://sites.google.com/site/proflucasscf
Linguagem C/C++
• Funções recursivas
– A recursão é o ato de uma função chamar a 
si própria;si própria;
– Em funções recursivas devemos nos 
preocupar com um critério de parada
• Irá determinar quando a função deixará de chamar 
a si própria
• Condição que evita a chamada infinita de funções 
recursivas
Linguagem C/C++
• Funções recursivas
– Alguns algoritmos são mais eficientes quando 
feitos de maneira recursiva, mas devemos feitos de maneira recursiva, mas devemos 
evitar sempre que possível.
• Se usada incorretamente tende a consumir muita 
memória e ser lenta.
• Obs.: A memória é consumida cada vez que o 
computador faz uma chamada a uma função
Linguagem C/C++
• Funções recursivas
– Dado um número inteiro n, podemos fazer a 
soma de todos os números, de 1 até o soma de todos os números, de 1 até o 
número n informado. (PA)
1 + ... + (n – 2)+ (n – 1) + n
Linguagem C/C++
• Exemplo (reproduza no compilador)
#include <iostream>
#include <stdio.h>
int soma(int n)
{{
if(n == 1)
return 1;
else
return ( n + soma(n-1) );
}
int main()
{
int n;
printf("Digite um inteiro positivo: ");
scanf("%d", &n);
printf("Soma: %d\n", soma(n));
}
Linguagem C/C++
• Funções recursivas
– Dado um número inteiro n, podemos fazer a 
multiplicação de todos os números, de 1 até o multiplicação de todos os números, de 1 até o 
número n informado. Com esta operação 
encontramos o valor Fatorial de um número 
n.
1 * ... * (n – 2) * (n – 1) * n
Linguagem C/C++
• Exemplo (reproduza no compilador)
#include <iostream>
#include <stdio.h>
int fatorial(int n)
{{
if(n == 1)
return 1;
else
return ( n * fatorial(n-1) );
}
int main()
{
int n;
printf("Digite um inteiro positivo: ");
scanf("%d", &n);
printf("Fatorial: %d\n", fatorial(n));
}
Linguagem C/C++
• Exercício no Laboratório!!!
– Imagine um casal de coelhos recém nascidos, supondo que 
após um mês esse casal possa procriar, gerando um novo casal 
de coelhos. Por sua vez, esse novo casal, após um mês, dê de coelhos. Por sua vez, esse novo casal, após um mês, dê 
origem a um novo casal. Supondo que a cada procriação não 
haja nenhuma morte, quantos coelhos seriam gerados em seis 
meses?
De acordo com o enunciado do problema, temos a seguinte 
progressão de números:
1 1 2 3 5 8 ...
Note que cada número é igual à soma dos dois anteriores. 
Linguagem C/C++
• Exercício no Laboratório!!!
Na natureza, alguns fenômenos parecem obedecer a um padrão 
numérico - como é o caso a velocidade com que os coelhos se 
reproduzem. O mais intrigante é que esses números guardam, reproduzem. O mais intrigante é que esses números guardam, 
entre si, uma proporção áurea. Essa seqüência de números é 
chamada de seqüência de Fibonacci.
Logo:
Faça um algoritmo recursivo que dado um valor de entrada n, 
calcule toda a seqüência de Fibonacci até este n-ésimo 
número informado (digitado pelo usuário).