11. FUNÇÕES RECURSIVAS
24 pág.

11. FUNÇÕES RECURSIVAS


DisciplinaProgramacao Modular91 materiais1.043 seguidores
Pré-visualização2 páginas
Funções Recursivas
Alguns slides retirados de: 
ROSA, J. L. G. SCC120 - Capítulo 8 Funções 
Recursivas em C. http://www.icmc.usp.br/~joaoluis. 
2010.
LARA, S. M. A. de. Recursão em C. Universidade de 
São Paulo \u2013 São Carlos \u2013 Instituto de Ciências 
Matemáticas e de Computação. 2010.
Funções Recursivas
\u2022 A recursão é uma técnica que define 
um problema em termos de uma ou 
mais versões menores deste mesmo 
problema 
\u2022 Esta ferramenta pode ser utilizada 
sempre que for possível expressar a 
solução de um problema em função do 
próprio problema 
03/08/13
3
Funções Recursivas
\uf06e Funções e procedimentos recursivos são 
aqueles que apresentam como 
característica poder chamar a si próprios.
\uf06e A cada nova chamada da função ou sub-
rotina as anteriores ficam suspensas até 
esta última ser resolvida.
\uf06e Quando a última for resolvida haverá um 
retorno sucessivo das chamadas, 
resolvendo-as uma a uma.
Funções Recursivas
\u2022 Trazendo a recursividade para o nosso cotidiano um ótimo 
exemplo está na ação de contar um saco de moedas, onde a 
cada ato de retirar uma moeda do saco precisa-se \u201ccontar 
dinheiro\u201d que corresponde a identificar qual é o valor da 
moeda e somá-la à quantia que ainda está no saco.
\u2022 Para identificar a quantia que ainda está no saco basta chamar 
a mesma função \u201ccontar dinheiro\u201d novamente, porém dessa 
vez já considerando que essa moeda não está mais lá.
\u2022 E este processo de retirar uma moeda, identificar seu valor e 
somar com o restante do saco se repete até que o saco esteja 
vazio, quando atingiremos o ponto de parada e a função 
retornará o valor zero, indicando que não há mais moedas no 
saco.
03/08/13
Funções Recursivas
\u2022 Nesse ponto a função \u201ccontar dinheiro\u201d foi 
chamada um número de vezes igual a 
quantidade de moedas no saco, e a última 
chamada começa a devolver os valores de 
retorno de cada instância da função, iniciando 
por zero (saco vazio), somado ao valor da 
última moeda, da penúltima, etc, até retornar à 
primeira chamada referente a primeira moeda, e 
nesse momento a função inicial se encerra 
trazendo como valor de retorno a soma dos 
valores de todas as moedas que estavam no 
saco.
03/08/13
6
Funções Recursivas
\uf06e O conceito de recursão pode 
simplificar a elaboração de soluções 
para determinados tipos de problema.
\uf06e Mas, por questões de limitações de 
espaço de memória, ou tempo, as 
soluções não recursivas sejam 
preferidas.
Funções e Sub-rotinas 
Recursivas
\u2022 Quando a recursão acontece, várias ações 
ocorrem:
\u2022 A função começa a execução do seu primeiro 
comando cada vez que é chamada; 
\u2022 Novas e distintas cópias dos parâmetros 
passados por valor e variáveis locais são 
criadas;
\u2022 A posição que chama a função é colocada 
em estado de espera, enquanto que o nível 
gerado recursivamente esteja executando.
03/08/13
Funções e Sub-rotinas 
Recursivas
\u2022 Cada vez que uma função é chamada de 
forma recursiva, é guardada uma cópia 
dos seus parâmetros de forma a não 
perder os valores dos parâmetros das 
chamadas anteriores. 
\u2022 Em cada instância da função, só são 
diretamente acessíveis os parâmetros 
criados para esta instância, não sendo 
acessíveis os parâmetros de outras 
instâncias.
03/08/13
9
Funções e Sub-rotinas 
Recursivas
\uf06e Todo cuidado é pouco ao se fazer funções 
recursivas. 
\uf06e A primeira coisa a se providenciar é um 
critério de parada. 
\uf06e Este vai determinar quando a função deverá 
parar de chamar a si mesma, impedindo 
uma recursividade sem fim.
\uf06e Um ponto importante a ser considerado é 
que cada vez que a função é chamada 
recursivamente, ela deve estar mais 
próxima de satisfazer a condição básica, 
que é a condição de interrupção da 
recursividade.
Funções Recursivas \u2013 
Exemplo com a main
/*ProgC095.cpp - Primeira Recursão*/
#include <iostream>
using namespace std;
int main (){
int a, b, c, opcao;
cout <<&quot;Digite o valor de A: &quot;; cin >> a;
cout <<&quot;Digite o valor de B: &quot;; cin >> b;
c=a+b;
cout <<&quot;O resultado de A + B e &quot;<<c<<&quot;\n\n&quot;;
cout << &quot;Deseja reiniciar o programa e realizar outro calculo?\n1. Sim\t2.Nao\n\n=> &quot;;
cin >> opcao;
if (opcao==1)
 main();
else
 return 0; }
Condição de parada
Chamada da função main(), repete 
todo o programa
Para a execução
Funções Recursivas
\u2022 Há certos algoritmos que são mais eficientes 
quando feitos de maneira recursiva, mas a 
recursividade quando usada incorretamente, 
tende a consumir muita memória e ser 
lenta. 
\u2022 A memória é consumida cada vez que o 
computador faz uma chamada a uma 
função. 
\u2022 Com funções recursivas a memória do 
computador pode se esgotar rapidamente. 
03/08/13
Funções Recursivas - 
Exemplo
//ProgC096.cpp - SOMATORIO Recursivo
#include <iostream>
int somatorio(int x) {
 if( x == 1 )
 return 1;
 else
 return(x + somatorio(x -1));
 }
int main() {
 int num;
 std::cout << &quot;Entre com um numero: &quot;;
 std::cin >> num;
 std::cout << &quot;O somatorio de 0 ate &quot; << num << &quot; e: &quot; 
 << somatorio(num) << &quot;\n&quot;;
 return 0; }
Função Recursiva
Condição de parada
Chamada Recursiva
Chamada Inicial
Funções Recursivas - 
Exemplo
Funções Recursivas - Exemplo
/*ProgC097.cpp - Escrever uma 
sequência de números*/
#include <iostream>
using namespace std;
void esc_numero1(int num){
 if (num > 0) {
 esc_numero1(num-1);
 cout << num << &quot; &quot;; } }
void esc_numero2(int num) {
 if (num > 0) {
 cout << num << &quot; &quot;;
 esc_numero2(num-1); } }
int main() {
 int numero;
 cout << &quot;Introduza o numero 
inicial (>0)&quot;;
 cin >> numero;
 cout << endl;
 esc_numero1(numero);
 cout << endl;
 esc_numero2(numero);
 cout << endl;
 return 0;}
Função Recursiva
Função Recursiva
Condição 
de parada
Condição 
de parada
Chamada 
Recursiva
Chamada 
Recursiva
Chamada Inicial
Chamada Inicial
Funções Recursivas - Exemplo
03/08/13
esc_numero1(4)
esc_numero1(3)
esc_numero1(2)
esc_numero1(1)
esc_numero1(0) Para as chamadas
Escreve 1 na tela
Escreve 2 na tela
Escreve 3 na tela
Escreve 4 na tela esc_numero2 (4)
Escreve 4 na tela
esc_numero2 (3)
Escreve 3 na tela
esc_numero2 (2)
Escreve 2 na tela
esc_numero2 (1)
Escreve 1 na tela
esc_numero2 (0)
Finaliza todas as 
chamadas
16
Funções e Sub-rotinas 
Recursivas - Exemplo
/*ProgC098 - Fatorial recursivo.*/
 #include <iostream>
 #include <cstdlib>
 using namespace std;
 long fatorial(int n);
 int main () {
 int n, cont;
 for(cont = 1; cont <= 10; cont++) {
 cout << &quot;\nDigite um numero: &quot;;
 cin >> n;
 cout << &quot;O fatorial de &quot; << n << &quot; e: &quot; << fatorial(n) << endl;
 }
 system(&quot;PAUSE&quot;);
 return 0;
 }
 long fatorial (int n) {
 if (n<=0)
 return 1;
 else
 return (long(n) * fatorial(n-1));
 }
Protótipo da função para calcular o 
fatorial de um número.
Chamada externa 
da função
Teste de parada da 
recursividade
Chamada interna da 
função
Funções Recursivas - Exemplo
03/08/13
fatorial (5)
5 * fatorial (4)
4 * fatorial (3)
3 * fatorial (2)
2 * fatorial (1)
1 * fatorial (0) 1 * 1
2 * 1
3 * 2
4 * 6
5 * 24
120
Funções Recursivas - 
Exemplo
/*ProgC099.cpp - FIBONACCI Recursivo*/
#include <iostream>
using namespace std;
int fibonacci(int N) {
 if( N == 1 ) return 1;
 else if(N == 2) return 1;
 else return(fibonacci(N-1) + fibonacci(N-2)); }
int main() {
 int num, F;
 cout << &quot;Entre com um numero: &quot;; cin >> num;
 cout << &quot;A serie de Fibonacci para &quot; << num << &quot; elementos e:\n&quot;;
 for(F=1;F <= num;F++) {
carol
carol fez um comentário
legal
0 aprovações
Carregar mais