LINGUAGEM: Linguagem C - Capítulo 2 - Parte 2

LINGUAGEM: Linguagem C - Capítulo 2 - Parte 2

Funções: main() e recursão

A função main()

O que main() devolve?

De acordo com o padrão ANSI, a função main() devolve um inteiro para o processo chamador, que é, geralmente, o sistema operacional.
Devolver um valor em main() é equivalente a chamar exit() com o mesmo valor.
Se main() não devolve explicitamente um valor, o valor passado para o processo chamador é tecnicamente indefinido.
Na prática, a maioria dos compiladores C devolve 0, mas não conte sempre com isso!

Pode-se também declarar main() como void.
Alguns compiladores geram uma ADVERTENCIA, se a função não é declarada como void e também não devolve um valor.

argc e argv - argumentos para main()



int main ( int argc, char * argv[] ) {
 
 for( ; argc -- ;  )
  printf("arg[%d] = %s\n", argc, argv[argc]);
}

Recursão

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.

Recursão é o processo de definir algo em termos de si mesmo e é, algumas vezes, chamado de definição circular.

Exemplos: 

#include <stdlib.h>
#include <string.h>

char * gnu(int n) {
    static char buf[1024];

    if (n == 0)
        strcpy(buf,"GNU");
    else {
            gnu(n-1);
            strcat(buf," Not Unix");
    }

    return buf;
}

char * gnu2(int n) {
    static char buf[1024];

    if (n == 0)
        return "GNU";
    else {
            char aux[1024];

            strcpy(aux,gnu2(n-1));
            sprintf(buf,"(%s %s)",aux,"Not Unix");
    }

    return buf;
}

int main(int argc, char * argv[]) {

        printf("%s\n", gnu(atoi(argv[1])) );
        printf("%s\n", gnu2(atoi(argv[1])) );

}
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 !
  • 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 !

Atividade 1 - Torres de HANOI

Em 1883, o matematico francesEdouard Lucas inventou o famoso quebra-cabeça das Torres de Hanoi, tambem conhecido por Torres de Brahma e contado em forma de lenda:


"No grande templo de Brahma em Benares, numa bandeja de metal sob a cúpula que marca o centro do mundo, três agulhas de diamante servem de pilar a sessenta e quatro discos de ouro puro. Incansavelmente, os sacerdotes transferem os discos, um de cada vez, de agulha para agulha, obedecendo sempre à lei imutável de Brahma: Nenhum disco se podera sobrepor a um menor.

No inıcio do mundo todos os sessenta e quatro discos de ouro, foram dispostos na primeira das três agulhas, constituindo a Torre de Brahma. No momento em que o menor dos discos for colocado de tal modo que se forme uma vez mais a Torre de Brahma numa agulha diferente da inicial, tanto a torre como o templo serão transformados em pó e o ribombar de um trovão assinalara o fim do mundo."
[http://www2.mat.ua.pt/rosalia/cadeiras/ADA/THpaper.pdf]


Escreva um programa em C, que simule o trabalho dos sacerdotes conforme descrito acima! 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.

int main(int c, char * v[]) {
/* assuma que atoi(v[1]) é o número n de discos a ser movido de um pilar para outro */

}

Atividade 2 - Combinações

Quantos times de futebol diferentes podem ser feitos com uma turma de 26 alunos?! No segundo grau, você DEVE ter aprendido que esta questão pode ser resolvida utilizando a fórmula mágica de COMBINAÇÕES:


Sendo n=26 e k=11
26! / [11! (26 - 11)!] = 26*25*24*23*22*21*20*19*18*17*16 / 11*10*9*8*7*6*5*4*3*2*1 
                        = 308403583488000/ 39916800
                        = 7726160

Bom, se você for escrever um programa em C para calcular combinações de n tomados k a k e utilizar a definição acima você poderá ter sérios problemas de overflow! Repare que o número 308403583488000 quando escrito em binário fica:
10  0011 000  0111 1101  1100 1110  0000 1010  1001 0000  0000 0000
Isto indica que são necessário 7 bytes no mínimo para armazená-lo na memória do computador. Por outro lado, se observarmos o resultado final 7726160 que em binário é
111 0101  1110 0100  0101 0000
vemos que ele ocupa apenas 3 bytes! Em resumo, usando inteiros de 4bytes podemos armazenar o resultado final mas não poderemos armazenar resultados intermediários como os acima apresentados! O que fazer?

Vamos pensar um pouco: queremos formar times de 11 num universo de 26 alunos. Do ponto de vista de um aluno particular, os times a serem formados podem ser divididos em duas classes: os times nos quais o aluno participa e os times nos quais ele não participa. Os times nos quais um particular aluno participa são em número de COMB( 25, 10 ). Ou seja, o referido aluno mais dez dentre os 25 restantes. Já os times nos quais o aluno não participa são em número de COMB( 25, 11 ). Ou seja, o aluno está excluído e são formados times de 11 dentre os 25 restantes.

Este raciocínio pode ser repetido recursivamente agora para COMB( 25, 10 ) e COMB( 25, 11 ). O resultado final é o seguinte padrão recursivo:



Agora, partindo da fórmula acima podemos escrever um programa recursivo que calcular combinações sem os problemas de overflow indicados acima quando usamos a definição tradicional de combinações. Tal programa poderia usar a função abaixo:
int comb(int n, int k) {
 if ( k > n )
  return 0;

 if ( k == 0 || k == n )
  return 1;
 else
  return comb(n-1,k-1) + comb(n-1,k);
}

Resolvemos um problema mas também criamos um outro: o de tempo de execução. Faça um teste. Tente calcular comb(36,11) usando a função acima. Observe quanto tempo vai demorar para obter o resultado!

O que fazer então?! Na raiz do problema está o fato de que a função recursiva proposta faz inumeras vezes o mesmo trabalho. Por exemplo: COMB(36,11) depende de COMB(35,10) e COMB(35,11). Já COMB(35,11) depende de COMB(34,10) e COMB(34, 11); e, COMB(35,10) depende de COMB(34,9) e COMB(34,10). Observe que esta última combinação - COMB(34,10) - aparece em dois ramos distintos de recursão e por isso irá ser calculado duas vezes!

Uma solução para evitar este trabalho todo é criar uma tabela para registrar cálculos já feitos:

int comb(int n, int k) {
 static int tab[50][50];

 if ( k > n )
  return 0;

 if ( tab[n][k] == 0 ) {
  if ( k == 0 || k == n )
   tab[n][k] = 1;
  else
   tab[n][k] = comb(n-1,k-1) + comb(n-1,k);
 }

 return tab[n][k];
}

Teste as funções apresentadas acima e verifique se realmente as idéias discutidas fazem sentido.

Leitura Recomendada

  • CCT capítulo 6

Exercícios

  1. Complete a atividade 1
  2. Na atividade 1, se cada disco pode ser movido de um lugar para outro em 1 nanosegundo (= 10-9 seg.), quanto tempo os monges irão levar para mover os 64 disco de uma torre para a outra?
  3. Complete a atividade 2
  4. Na atividade 2, qual os maiores k e n tais que comb(n,k) não estoure a representação baseada em int de 4 bytes?
  5. Defina uma função recursiva para determinar o maior divisor comum entre dois números naturais x e y, baseando-se nas regras abaixo. Em seguida, napresente uma versão iterativa do algoritmo capaz de realizar a mesma tarefa.
    • mdc(x,y) = x, se x = y
    • mdc(x,y) = mdc(y,x), se x < y
    • mdc(x.y) = mdc(x-y,y), se x > y
  6. Escreva uma função recursiva void fibo(int n); que gere os n primeiros termos da série de Fibonacci.
  7. Faça de conta que na linguagem C não existem operadores para adição, subtração, multiplicação e nem divisão. Imagine que existam apenas os operadores de incremento ++N e decremento --N. Usando como base apenas estes dois operadores- ++ e -- (quer dizer, você não deve usar os operadores +, -, * e /) -, defina funções recursivas para:
    • int soma(int x,int y); - retorna soma x mais y;
    • int subt(int x,int y); - retorna subtração x menos y;
    • int mult(int x,int y); - retorna multiplicação x vezes y;
    • int divi(int x,int y); - retorna divisão inteira x dividido por y;
  8. Defina uma rotina recursiva para, dado um natural n, imprimi-lo em base binária.

Bibliografia e fonte:


  • [CCT] Schildt, H. (1996) C, completo e total: 3a Ed.. São Paulo, Makron.
  • LP, UFMA; Coutinho, Lucian. Linguagem de programação para ciencia da computação da ufma.http://www.deinf.ufma.br/~lrc/2009.1/LP/
  • [K&R] KERNIGHAN, B. e RITCHIE, D. (1990) C, a linguagem de programação: padrão ANSI. Rio de Janeiro: Campus.
  • DEITEL, H. M. (1999) Como programar em C. Rio de Janeiro: LTC.
  • Módulo Consultoria e Informática (1989) Linguagem C: programação e aplicações. Rio de Janeiro: LTC.