Funcoes Recursivas

Prévia do material em texto

Programação e Estruturas de Dados 
Jaqueline Faria de Oliveira 
Mestre em Informática 
E-mail: jaqueline.oliveira@prof.unibh.br 
 
Funções Recursivas 
Recursividade 
• Uma função pode chamar a si própria, e 
nestes casos essa função é chamada de 
função recursiva. 
– Atenção: Todo cuidado é pouco ao se fazer 
funções recursivas: 
• A primeira coisa a se providenciar é um critério de 
parada. Este vai determinar quando a função deverá 
parar de chamar a si mesma. Isto impede que a função 
se chame infinitas vezes. 
Recursividade 
• Três pontos devem ser lembrados quando 
construímos uma função recursiva: 
1. Definir o problema em termos recursivos. 
2. Definir um passo básico (ou mais) cujo resultado 
é imediatamente conhecido. 
3. Cada vez que a função é chamada 
recursivamente, deve estar mais próxima de 
satisfazer a condição básica. 
Recursividade 
Exemplo: Função que calcula o fatorial de um número inteiro n com 
uma função recursiva: 
 
#include <stdio.h> 
int fatorial(int n){ 
 if (n > 0) 
 return n*fat(n-1); 
 else return 1; 
} 
main(){ 
 int n, fat; 
 printf("\n\nDigite um valor para n: "); 
 scanf("%d", &n); 
 fat = fatorial(n); 
 printf("\nO fatorial de %d e' %d", n, fat); 
} 
Recursividade 
• Função que calcula o fatorial de um número 
inteiro n com uma função recursiva. 
• Note que, enquanto n não for igual a 0, a 
função fat chama a si mesma, cada vez com 
um valor menor. 
• Quando n=0 a função para sua execução. 
Recursividade 
• Para entender o funcionamento de uma 
função recursiva podemos imginar da seguinte 
forma: 
– A cada nova chamada recursiva uma outra função 
idêntica é chamada. 
 
• O que ocorre na memória é quase a mesma 
coisa. 
Recursividade 
Exemplo: Uma chamada de fatorial onde n = 3: 
 
 
 
 
n = 3 
int fatorial(int n){ 
 if (3 > 0) 
 return n*fat(3-1); 
 else return 1; 
} 
 
n = 2 
int fatorial(int n){ 
 if (2 > 0) 
 return n*fat(2-1); 
 else return 1; 
} 
 
n = 1 
int fatorial(int n){ 
 if (1 > 0) 
 return n*fat(1-1); 
 else return 1; 
} 
 
n = 0 
int fatorial(int n){ 
 return 1; 
} 
 
Recursividade 
• Há certos algoritmos que são mais eficientes 
quando feitos de maneira recursiva, mas a 
recursividade é algo a ser evitado sempre que 
possível, pois, se usada incorretamente, tende 
a consumir muita memória e ser lenta. 
• Lembre-se que memória é consumida cada 
vez que o computador faz uma chamada a 
uma função. Com funções recursivas a 
memória do computador pode se esgotar 
rapidamente. 
Exercícios 
1. Crie uma função recursiva que receba um número 
inteiro positivo N e calcule o somatório dos números 
de 1 a N. 
 
2. Faça uma função recursiva que receba um número 
inteiro positivo N e imprima todos os números 
naturais de 0 até N em ordem crescente. 
 
3. Crie um programa em C, que contenha uma função 
recursiva que receba dois inteiros positivos k e n e 
calcule kn. Utilize apenas multiplicações. O programa 
principal deve solicitar ao usuário os valores de k e n 
e imprimir o resultado da chamada da função. 
Exercícios 
1. Crie uma função recursiva que receba um número inteiro 
positivo N e calcule o somatório dos números de 1 a N. 
Exercícios 
2. Faça uma função recursiva que receba um número 
inteiro positivo N e imprima todos os números naturais 
de 0 até N em ordem crescente. 
Referências 
• C Completo e Total. Terceira edição. Herbert 
Schildt. Editora Pearson. 
• Notas de aula professor Walisson Ferreira. 
• Programação e Estruturas de Dados em 
Linguagem C (PED). Pollyanna Miranda de 
Abreu.