INF 1007 Programação II  
Aula 06 Recursividade  
Edirlei Soares de Lima  
<elima@inf.puc-rio.br>  
Introdução  
As seguintes sentenças são Verdadeiras ou Falsas?  
1
2
3
. Alguém diz: “Estou mentido agora!”;  
. Alguém diz: “Esta sentença é falsa!”;  
. Um homem natural de Creta, em praça pública, anuncia: “Todo  
cretense é mentiroso!”;  
Introdução  
Definições Recursivas  
Em uma definição recursiva um item é definido em termos de  
si mesmo, ou seja, o item que está sendo definido aparece  
como parte da definição;  
Em todas as funções recursivas existe:  
Caso base (um ou mais) cujo resultado é imediatamente conhecido;  
Passo recursivo em que se tenta resolver um sub-problema do  
problema inicial.  
Definições Recursivas  
Função fatorial: ꢀꢁꢂ = × − 1 × × 1  
A função fatorial pode ser definida recursivamente como:  
Caso Base  
ꢁꢂ ꢃ =1 ×1 , > 0  
, ꢄꢅ ꢃ = 0  
Passo Recursivo  
Chamada Recursiva  
O caso base é uma situação trivial da função, onde calcular o  
valor da função é imediato e direto.  
Definições Recursivas  
Função fatorial: ꢀꢁꢂ = × − 1 × × 1  
A função fatorial pode ser definida recursivamente como:  
Caso Base  
ꢁꢂ ꢃ =1 ×1 , > 0  
, ꢄꢅ ꢃ = 0  
Passo Recursivo  
Chamada Recursiva  
O passo recursivo é a aplicação recursiva da função em uma  
versão de menor porte do problema.  
Definições Recursivas  
Solução Conceitual:  
Problema de Ordem-n:  
ꢁꢂ ꢃ : N N  
A função fat recebe um número  
natural n e retorna um número  
natural que é o fatorial de n  
Precondição:  
ꢃ ∈ N  
n só pode ser um número natural  
Se n é zero, a função fat retorna 1  
valor de fat para n-1 é necessário  
Caso(s) Base:  
ꢃ = 0 ꢀꢁꢂ = 1  
Chamada Recursiva:  
ꢁꢂ ꢃ 1  
Passo Recursivo:  
ꢁꢂ ꢃ = ∗ ꢀꢁꢂ 1  
A função fat retorna o valor de n  
multiplicado pelo valor de fat para  
n-1  
Funções Recursivas  
Na programação, uma função recursiva é aquela que faz uma  
chamada para si mesma;  
Essa chamada pode ser:  
Direta: uma função A chama a ela própria  
Indireta: função A chama uma função B que, por sua vez, chama A  
void func_rec(int n)  
{
.
..  
func_rec(n-1);  
..  
Recursao Direta  
.
}
Funções Recursivas  
Função recursiva para cálculo de fatorial:  
Caso Base  
Passo Recursivo  
ꢁꢂ ꢃ =1  
, ꢄꢅ ꢃ = 0  
ꢃ × ꢀꢁꢂ ꢃ − 1 , ꢄꢅ ꢃ > 0  
Chamada Recursiva  
int fat(int n)  
{
if (n==0)  
Caso Base  
return 1;  
else  
Passo Recursivo  
return n * fat(n-1);  
}
Funções Recursivas  
Comportamento de uma função recursiva:  
Quando uma função é chamada recursivamente, cria-se um ambiente  
local para cada chamada;  
As variáveis locais de chamadas recursivas são independentes entre si,  
como se estivéssemos chamando funções diferentes;  
Funções Recursivas  
include <stdio.h>  
#
int fat(int n)  
{
int f;  
if (n == 0)  
f = 1;  
else  
f = n * fat(n-1);  
return f;  
}
int main(void)  
{
int n = 3, r;  
r = fat(n);  
printf("Fatorial de %d = %d \n", n, r);  
return 0;  
}
Funções Recursivas  
include <stdio.h>  
#
int fat(int n)  
{
int f;  
if (n == 0)  
f = 1;  
else  
f = n * fat(n-1);  
return f;  
}
int main(void)  
{
int n = 3, r;  
r = fat(n);  
printf("Fatorial de %d = %d \n", n, r);  
return 0;  
}
Funções Recursivas  
include <stdio.h>  
#
int fat(int n)  
{
int f;  
if (n == 0)  
f = 1;  
else  
f = n * fat(n-1);  
return f;  
}
int main(void)  
{
int n = 3, r;  
r = fat(n);  
printf("Fatorial de %d = %d \n", n, r);  
return 0;  
}
Funções Recursivas  
include <stdio.h>  
#
int fat(int n)  
{
int f;  
if (n == 0)  
f = 1;  
else  
f = n * fat(n-1);  
return f;  
}
int main(void)  
{
int n = 3, r;  
r = fat(n);  
printf("Fatorial de %d = %d \n", n, r);  
return 0;  
}
Funções Recursivas  
include <stdio.h>  
#
int fat(int n)  
{
int f;  
if (n == 0)  
f = 1;  
else  
f = n * fat(n-1);  
return f;  
}
int main(void)  
{
int n = 3, r;  
r = fat(n);  
printf("Fatorial de %d = %d \n", n, r);  
return 0;  
}
Funções Recursivas  
include <stdio.h>  
#
int fat(int n)  
{
int f;  
if (n == 0)  
f = 1;  
else  
f = n * fat(n-1);  
return f;  
}
int main(void)  
{
int n = 3, r;  
r = fat(n);  
printf("Fatorial de %d = %d \n", n, r);  
return 0;  
}
Funções Recursivas  
include <stdio.h>  
#
int fat(int n)  
{
int f;  
if (n == 0)  
f = 1;  
else  
f = n * fat(n-1);  
return f;  
}
int main(void)  
{
int n = 3, r;  
r = fat(n);  
printf("Fatorial de %d = %d \n", n, r);  
return 0;  
}
Funções Recursivas  
include <stdio.h>  
#
int fat(int n)  
{
int f;  
if (n == 0)  
f = 1;  
else  
f = n * fat(n-1);  
return f;  
}
int main(void)  
{
int n = 3, r;  
r = fat(n);  
printf("Fatorial de %d = %d \n", n, r);  
return 0;  
}
Funções Recursivas  
include <stdio.h>  
#
int fat(int n)  
{
int f;  
if (n == 0)  
f = 1;  
else  
f = n * fat(n-1);  
return f;  
}
int main(void)  
{
int n = 3, r;  
r = fat(n);  
printf("Fatorial de %d = %d \n", n, r);  
return 0;  
}
Funções Recursivas  
Exercício: forneça a definição recursiva para a operação  
de potenciação:  
Caso Base  
=1, = 0  
ꢆ ×(), ꢄꢅ ꢃ > 0  
Passo Recursivo  
int pot(int x, int n)  
{
if (n == 0)  
return 1;  
else  
return x * pot(x, n-1);  
}
Manipulação de Cadeias de Caracteres  
É possível utilizar funções recursivas para manipular  
cadeias de caracteres;  
Baseiam-se em uma definição recursiva de cadeias  
de caracteres:  
Uma cadeia de caracteres é:  
a cadeia de caracteres vazia; ou  
um caractere seguido de uma cadeia de caracteres.  
Manipulação de Cadeias de Caracteres  
Implementação recursiva da função “imprime”:  
void imprime_rec(char* s)  
{
if (s[0] != '\0')  
{
printf("%c", s[0]);  
imprime_rec(&s[1]);  
}
}
int main (void)  
{
char cidade[] = "Rio de Janeiro";  
imprime_rec(&cidade[0]);  
return 0;  
}
Manipulação de Cadeias de Caracteres  
Implementação recursiva da função “imprime invertido”?:  
void imprime_inv(char* s)  
{
if (s[0] != '\0')  
{
imprime_inv(&s[1]);  
printf("%c", s[0]);  
}
}
int main (void)  
{
char cidade[] = "Rio de Janeiro";  
imprime_inv(&cidade[0]);  
return 0;  
}
Manipulação de Cadeias de Caracteres  
Implementação recursiva da função “comprimento”?:  
int comprimento(char s[])  
{
versão iterativa  
int i, n = 0;  
for (i=0; s[i] != '\0'; i++)  
{
n++;  
}
return n;  
}
int comprimento_rec(char* s)  
{
versão recursiva  
if (s[0] == '\0')  
return 0;  
else  
return 1 + comprimento_rec(&s[1]);  
}
Leitura Complementar  
Waldemar Celes, Renato Cerqueira, José Lucas  
Rangel, Introdução a Estruturas de Dados, Editora  
Campus (2004).  
Capítulo 4 Funções