12.recursao

Prévia do material em texto

Recursão 
Funções 
Conceito 
 Em C, como virtualmente em todo 
linguagem de programação, funções podem 
chamar a si mesmas, direta ou 
indiretamente. 
 Uma função é dita recursiva se em seu 
corpo a uma chamada (direta ou indireta) 
para si mesma. 
 
 
2 
Conceito 
 Recursão é o processo de definir algo em 
termos de si mesmo e é, algumas vezes, 
chamado de definição circular. 
3 
Exemplos 
1. char * gnu(int n) { 
2. static char buf[1024]; 
 
3. if (n == 0) 
4. strcpy(buf,"GNU"); 
5. else { 
6. gnu(n-1); 
7. strcat(buf," Not Unix"); 
8. } 
 
9. return buf; 
10. } 
 
4 
Exemplos 
1. char * gnu2(int n) { 
2. static char buf[1024]; 
 
3. if (n == 0) 
4. return "GNU"; 
5. else { 
6. char aux[1024]; 
 
7. strcpy(aux,gnu2(n-1)); 
8. sprintf(buf,"(%s %s)",aux,"Not Unix"); 
9. } 
 
10. return buf; 
11. } 
 
5 
Observações 
 Quando uma função chama a si mesma, 
novos parâmetros e variáveis locais - 
quando estas não são static - são alocados 
na pilha e o código da função é executado 
com essas novas variáveis. 
 No caso de variáveis locais static, todas as 
chamadas recursivas compartilham a 
mesma variável ! 
 
6 
Observações 
 Quando cada chamada recursiva retorna, 
as variáveis locais (não static) e os 
parâmetros são removidos da pilha e a 
execução recomeça do ponto da chamada à 
função dentro da função. 
 Ao escrever funções recursivas, você deve 
ter um comando if em algum lugar para 
forçar a função a retornar sem que a 
chamada recursiva seja executada mais 
uma vez ! 
7 
Atividade 1 - Hanoi 
 Escreva um programa em C, que simule o 
trabalho dos sacerdotes conforme descrito 
< 
http://www2.mat.ua.pt/rosalia/cadeiras/AD
A/THpaper.pdf > 
 Na lenda, os sacerdotes movem 64 discos. 
No seu programa, trabalhe com n discos, 
onde n é um número informado pelo 
usuário. Dica: usando recursão, o seu 
programa ficará bastante compacto. 
 
8