Programação de Computadores - Recursão

Prévia do material em texto

Universidade Estadual do Centro Oeste - UNICENTRO
Departamento de Ciência da Computação - DECOMP
Programação de Computadores II
RecursãoRecursão
Professora: Inali Wisniewski Soares
Recursão (1)
� Uma função que chama a si mesma é dita recursiva.
� Recursividade permite descrever algoritmos de forma
mais clara e concisa, especialmente problemas recursivos
por natureza ou que utilizam estruturas recursivas.
� Normalmente, as funções recursivas são divididas em 
duas partes
� Chamada Recursiva
� Condição de Parada ou Caso Base - é fundamental para evitar a 
execução de loops infinitos.
2
Exemplo Fatorial
� O fatorial de um número inteiro não negativo n, escrito
como n! (diz-se ‘n fatorial’) é o produto de todos os
números inteiros entre n e 1
n! = n x (n-1) x (n-2) x (n-3) x... x 1
ou
n! = n x (n-1)!n! = n x (n-1)!
� Por exemplo, 5! É o produto 5 * 4 * 3 * 2 * 1 = 120.
3
Exemplo 1 – Função Fatorial Iterativa
#include <stdio.h>
int Fatorial(int n);
int Fatorial(int n){
int i, fat = 1;
for (i = 1; i <= n; i++)
fat = fat * i;
return fat;
}}
int main(void) {
int num;
scanf("%d",&num);
printf("Fatorial de %d = %d ", num, Fatorial(num));
return 0;
}
4
Exemplo 2 – Função Fatorial Recursiva (1)
� A função seguinte calcula o fatorial de n (n!) 
recursivamente, usando a fórmula n! = n × (n – 1)!:
int Fatorial(int n)
{
if (n <= 1) /*condição de parada*/
return 1;
elseelse
return n * Fatorial(n - 1); /*chamada recursiva*/
}
5
Exemplo 2 – Função Fatorial Recursiva (2)
#include <stdio.h>
int Fatorial(int n);
int Fatorial(int n){
if (n <= 1)
return 1;
else
return n * Fatorial(n - 1);
}
int main(void) {
int num;
scanf("%d",&num);
printf("Fatorial de %d = %d ", num, Fatorial(num));
return 0;
}
6
Como o compilador executa a recursão
� Internamente, quando qualquer chamada de função é feita
dentro de um programa, é criado um registro de ativação
na Pilha de Execução do programa.
� O registro de ativação armazena os parâmetros e
variáveis locais da função bem como o “registro devariáveis locais da função bem como o “registro de
retorno” no programa ou subprograma que chamou essa
função.
� Ao final da execução dessa função, o registro é
desempilhado e a execução é retomada de acordo com a
informação armazenada no “registro de retorno”.
7
Empilhamentos de contextos de execução
�Durante a execução do programa fatorial teremos na
memória, os seguintes estados para calcular
recursivamente o fatorial de 3:
Chamadas
Estado das pilhas N FAT Estado das pilhas N FAT 
1ª chamada (empilha) 3 3 * FAT(2)
2ª chamada (empilha) 2 2 * FAT(1)
3 3 * FAT(2)
3ª chamada (empilha) 1 1
2 2 * FAT(1)
3 3 * FAT(2)
8
Desempilhamento de contextos de execução
Retorno
Estado das pilhas N FAT
1º retorno (desempilha) 1 1
2 2 * FAT(1)
3 3 * FAT(2)
2 º retorno (desempilha) 2 2 * 1 = 2
3 3 * FAT(2)
3 º retorno (desempilha) 3 3 * 2 = 6
9
Recursão X Iteração (1)
� Tanto a iteração como a recursão se baseiam em uma 
estrutura de controle:
� a iteração usa uma estrutura de repetição;
� a recursão usa uma estrutura de seleção.
Os dois métodos envolvem repetições:� Os dois métodos envolvem repetições:
� iteração usa explicitamente uma estrutura de repetição;
� recursão obtém repetição por intermédio de chamadas 
repetidas de funções. 
10
Recursão X Iteração (2)
� Os dois métodos envolvem um teste de encerramento:
� iteração termina quando uma condição de continuação de laço se 
torna falso;
� recursão termina quando um caso básico é reconhecido. 
� Desvantagens da utilização de recursão
A recursão faz repetidas chamadas à função, isso pode custar caro, � A recursão faz repetidas chamadas à função, isso pode custar caro, 
tanto em tempo de processador como em espaço de memória. Os 
valores das variáveis que estão sendo processados tem de ser 
mantidos em pilhas.
11
Recursão X Iteração (3)
� Vantagens da utilização de recursão
� Criar versões mais claras e simples de algoritmos. 
Exemplos: o algoritmo de ordenação QuickSort (método de ordenação) é 
muito difícil de implementar de forma iterativa; muitos problemas 
relacionados com inteligência artificial também são resolvidos mais facilmente 
utilizando recursão. 
� Escolher recursão quando:� Escolher recursão quando:
� o problema pode ser resolvido de modo mais natural, resultando em 
programas mais fáceis de compreender;
� uma solução iterativa não é fácil de ser encontrada. 
12
Recursão X Iteração (4)
� Os dois métodos envolvem um teste de encerramento:
� iteração termina quando uma condição de continuação de 
laço se torna falso;
� recursão termina quando um caso básico é reconhecido. 
� Desvantagens da utilização de recursão� Desvantagens da utilização de recursão
� A recursão faz repetidas chamadas à função, isso pode custar 
caro, tanto em tempo do processador como em espaço de 
memória.
13
Exercício (1)
#include <stdio.h>
void recursao(int n);
void recursao(int n) {
if (n > 0){
printf(" %d ",n);
recursao(n-1);
}
}
Qual será a saída da variável n se 
o valor inserido
para n for 4?
int main(void) {
int x;
printf("Insira um numero inteiro");
scanf("%d",&x);
recursao(x);
return 0;
}
14
Exercício (2)
#include <stdio.h>
void recursao(int n);
void recursao(int n) {
if (n > 0){
recursao(n-1);
printf(" %d ",n);
}
}
Qual será a saída da variável n se 
o valor inserido
para n for 4?
}
int main(void) {
int x;
printf("Insira um numero inteiro");
scanf("%d",&x);
recursao(x);
return 0;
}
15