sábado, 13 de julho de 2013

Recursividade

Recursão é o principio de que algo pode ser definido em termos de pedaços menores de si mesmo, na computação a recursividade é alcançada através do uso de funções recursivas, uma função recursiva realiza uma chamada de função para si mesma, aonde cada chamada trabalha de forma a refinar as sucessivas entradas  aproximando-o ao resultado final da solução.

Este estilo de desenvolvimento pode causar algum desconforto ao apresentar a resposta de um problema maior com uma rotina que chama a si própria, do que dividir o problema em vários pedaços e escrever as respectivas funções separadas, leva um tempo para acostumar-se a este estilo de programação.

Para começar, considere um problema simples como calcular o fatorial de um numero n, o fatorial de n, escrito n! é o produto de todos os números inteiros que precedem n até 1, por exemplo, 5! = 5 * 4 * 3 * 2 * 1, com a formula sendo:

n! = (n) (n – 1) (n – 2) ... (1)

Entretanto a expressão resultou de um processo iterativo,  aonde se subtrai um valor cada vez maior de n até alcançar 1. Buscar a resposta  de forma recursiva envolve encontrar o  padrão de recorrência, considere que os passos para n! aonde n será multiplicado pelo fatorial (n-1)!, com  n’ = n-1  resultando em  (n’)(n’-1)! e assim sucessivamente ao qual podemos definir formalmente como:




Descrevendo passo a passo o processo iterativo e recursivo temos:

ITERAÇÃO

RECURSÃO
5* (5-1)!

5* (5-1)!
5*4* (5-2)!

5*4* (4-1)!
5*4*3* (5-3)!

5*4*3* (3-1)!
5*4*3*2* (5-4)!

5*4*3*2* (2-1)!
5*4*3*2*1

5*4*3*2*1

Para ilustrar a computação de 5! usando a abordagem recursiva como descrita, visualiza-se o processo em duas partes, a primeira parte consiste em empilhar chamadas de rotinas sucessivamente até o ponto de encontrar a condição de termino, a condição de termino é o momento em que a rotina recursiva deixa de chamar a si mesma e retorna um valor, iniciando assim a segunda parte do processo ao desempilhar todas as chamadas de funções que retornam em ordem reversa, esta fase termina quando encontrar a chamada original, completando o processo recursivo.

F(5) =
5*F(4)








F(4) =
4*F(3)








F(3) =
3*F(2)








F(2) =
2*F(1)








F(1) =
1
CONDIÇÃO DE TERMINO



F(2)=
2*1






F(3) =
3*2






F(4) =
4*6






F(5) =
5*24





1ª PARTE
120






2ª PARTE


Para montar a função C de fatorial, terá como entrada o numero positivo n para calcular o fatorial recursivamente, sendo a entrada menor ou igual a 1, isto é 0 e 1, retornamos 1, pois 0! e 1! são ambos definidos como 1, servindo assim como a condição de termino, do contrario a função retorna o resultado de n vezes o fatorial de n-1, como mostrado no detalhamento para o calculo de fatorial de 5.

#include <stdio.h>

unsigned int fact(unsigned int n)
{
      if (n > 1) {
            return( n * fact(n-1) );
      }
      else {
            return 1;
      }
}

void main(void)
{
      unsigned int i;

      i = fact(5);

      printf("5! = %u\n", i);
}


Analisando a maneira que as funções são executadas em C, precisa compreender como um programa fica organizado na memória,  fundamentalmente um programa consiste em 4 áreas:
1)      Código: instruções de maquina que são executadas no programa
2)      Dados estáticos: informações que se mantém durante todo o programa, como variável global e estática.
3)      Heap: espaço para armazenamento dinâmico, como a memória reservada para rotinas como alloc.
4)      Pilha: armazena as informações das chamadas de funções. O bloco de armazenamento colocado na pilha é conhecido como registro de ativação (stack frame), composto por:
a.       Parâmetros de entrada
b.      Valor de retorno
c.       Armazenamento temporário
d.      Copia do estado (registradores)
e.      Parâmetros de saída

PROGRAMA

STACK
CODIGO

Parâmetro de entrada
DADOS ESTATICOS



Valor de retorno
STACK

Armazenamento temporário





Copia do estado


HEAP

Parâmetro de saída





Retornando ao exemplo de calcular 5!, a área da pilha da execução do programa em C a cada chamada fica:


n=5

n=5

n=5

n=5

n=5

n=5

n=5

n=5

n=5
?

?

?

?

?

?

?

?

120

























n=4

n=4

n=4

n=4

n=4

n=4

n=4

n=4

n=4


?

?

?

?

?

?

24































n=3

n=3

n=3

n=3

n=3

n=3

n=3






?

?

?

?

6





































n=2

n=2

n=2

n=2

n=2










?

?

2











































n=1

n=1

n=1














1





























































A pilha é uma solução boa para armazenar informação paras as chamadas de função, graças ao seu comportamento ultimo a entrar, primeiro a sair (LIFO), entretanto seu uso possui fatores contra, manter informações de cada chamada executada pela rotina até seu retorno consome um espaço considerável, adicione também o tempo necessário para salvar e restaurar informações do registro de ativação (stack frame).

Tais preocupações devem ser levadas em conta, recursão é um principio elogiado nos meios acadêmicos como poderoso e elegante, o que não acontece em meios práticos, aonde elaborações profissionais tende a abominar esse tipo de resposta devido aos problemas que um código recursivo agrega.

No livro Code Complete escrito por Steve McConnel apesar de expressar que o uso seletivo da recursividade agrega benefícios, isso não o impede de afirmar que se um programador que trabalha para ele usar recursividade para calcular um fatorial, contrataria outra pessoa (forma elegante de dizer que demitiria).

Entre as opiniões reacionárias do escritor sobre o assunto, temos as seguintes regras para o bom uso da recursão:
1.       Certifique-se de que a recursividade pare.
2.       Use contadores de segurança para evitar a recursividade infinita.
3.       Restrinja a recursividade a uma única rotina (A chama B, que chama C, que chama A).
4.       Fique atento a pilha.
5.       Nunca calcule fatorial ou números de Fibonacci com recursão.

A ironia do texto deve servir como aviso para um trecho discutido anteriormente em ponteiros, código mal planejado resulta em erros catastróficos. Tanto o mau uso de ponteiros, como o uso incorreto da recursividade gera problemas difíceis de detectar, prefira sempre uma solução iterativa.

unsigned int ifact(unsigned int n)
{
      unsigned int i;

      for (i = (n-1); i > 0; --i)
            n *= i;

      return n;
}

quinta-feira, 4 de julho de 2013

Problema de Josephus

CÓDIGO-FONTE:
https://github.com/r-bauer/josephus/archive/master.zip


Na matemática um exemplo famoso de recorrência é atribuído a Flavius Josephus, um famoso historiador do primeiro século, que durante a guerra Judaica, se encontrava entre um bando de 41 judeus rebeldes encurralados pelos romanos em uma caverna.

Sem chance de fuga o grupo decide pela morte ao invés do aprisionamento, os rebeldes formam um circulo e começariam a partir de certo ponto pular duas pessoas e a matar a terceira pessoa numa direção fixa, a eliminação procede em torno do circulo que irá se tornando menor conforme as pessoas mortas são removidas, até não restar alguém vivo.

Conta à lenda que graça ao talento matemático de Josephus o mesmo conseguiu escapar desta tolice quanto ao suicídio ao encontrar o local no circulo inicial em que será o ultimo.

Determinada a tarefa, para buscar uma solução simples, podemos analisar a simulação grafica, com o seguinte circulo inicial:

Através da imagem percebe-se que a representação ideal para este tipo dado seria criar uma fila circular como primeiro passo.


Após o primeiro ciclo encontramos a fila circular com os elementos removidos, com as setas apontando para o elemento seguinte que continua na fila, associando assim ao tratamento de remoção feito por uma lista encadeada.



Uma lista pode armazenar o valor de forma mais intuitiva do que um vetor, que adicionaria um tratamento para mover os valores de índice no circulo inicial a cada exclusão, através da lista encadeada cada elemento mantém como informação o valor da posição original, descartando qualquer operação que não seja a de remover.


A solução reside no valor armazenado no ultimo nó a permanecer na lista encadeada

Ultimo ponto deve ser considerado antes programar a solução, Flavius Josephus atribui em sua biografia que devido à sorte ou a mão de Deus, ele e outro homem resolveram se entregar aos romanos, fato que inclui uma variação no problema, uma vez que historiadores consideram o tal homem como um cúmplice de Josephus, como a morte era administrada pela próxima escolha na fila, a forma de Josephus evitar o ato de assassinar um colega implica que ele colocou alguém de comum acordo para se render na penúltima posição.

Fugindo do tópico, gostaria de deixar indicado o filme cômico A vida de Brian feito pelo Monty Python narrando às engraçadas desventuras de um pobre judeu ante aos romanos, motivo pelo qual a fuga de Josephus sempre me faz associar com está película.

Para o código exemplo a ser apresentado, será utilizadas as rotinas mostradas em lista encadeada genérica parte 1 e parte 2, com a devida adaptação, a primeira é o formato do nó a ser utilizado que irá manter o numero da posição inicial no circulo, sua declaração no arquivo llapp.h resulta em:

// A lista de noh consiste em:
typedef struct tagSNODEDATA
{
    unsigned int uPos;     // posicaoh da pessoa na fila
}SNODEDATA;

                Para resolver o problema, ao criar a lista para simulação os dados que serão inseridos com a função a rotina AddNodeAtHead com valores já ordenados.

      L = CreateLList(  CreateData,
                        DeleteData,
                        DuplicatedNode,
                        NodeDataCmp);

      for (iCount = 1; iCount <= iPerson; ++iCount)
            AddNodeAtHead(L, &iCount);

                Tendo a criação da lista sido concluída, o resultado que se tem na memória é:

Head
41
40
39
38
37
36
35
......
7
6
5
4
3
2
1
Tail

O que descarta as operações de comparação, duplicados e ordenação da lista que devem ser incluídas no arquivo llapp.c, DuplicateNode e NodeDataCmp, não serão chamadas, enquanto que DeleteData não precisa de processamento adicional pelo tipo simples de dados armazenado.

BOOL  DeleteData(void *data)
{
    free( data );
    return TRUE;
}

int   DuplicatedNode(SLINK slkNewNode, SLINK slkListNode)
{
    return 2; // nunca serah chamada
}

int   NodeDataCmp(void *first, void *second)
{
    return ( 0 );       // nunca serah chamada
}
               
Somente a implementação de CreateData será necessária.

void *CreateData(void *data)
{
      SNODEDATA *pNewData;

      // aloca sua estrutura de dados
      pNewData = (SNODEDATA *) malloc(sizeof(SNODEDATA));
      // move os valores para a estrutura de dados
      pNewData->uPos = *((int *) data);
      // retorna o endereco da estrutura
      return (pNewData);
}

                Agora resta percorrer a lista como se está fosse um circulo, para tanto o seguinte trecho do código demonstra como a tarefa será efetivada.

slQueue = L->slkTail;
while (1)
{
      // avancah para o proximo noh
      slQueue = slQueue->prior;
      // terminou de percorrer a lista
      if (slQueue == NULL)
            // transforma a lista em uma fila circular
            slQueue = L->slkTail;
}

                Dentro deste laço será incluído o contador de eliminação iCount que ao atingir o valor iSeq exclui o nó, reiniciando a contagem, processo que irá se repetir até o momento que eliminar todos os nós da lista, controlado pela variável L->uiCount que armazena o total de nós presentes.

Ao tornar a lista em uma fila circular, os ponteiros que indicam inicio (L->slkHead) e fim (L->slkTail) deveriam apontar-se entre si, como tal mudança implicaria em alterar as rotinas genéricas para este tipo de suporte, foi descartada, outra opção também ignorada seria fazer verificações quanto ao elemento ser de inicio ou fim. A solução mais simples foi incluir a variável slDel para indicar o elemento a ser excluído, funcionando como ponteiro para a posição previa.

slQueue = L->slkTail;
iCount = 1;
while (L->uiCount)
{
      slDel = slQueue;
      slQueue = slQueue->prior;
      if (slQueue == NULL)
            slQueue = L->slkTail;

      // conta ateh achar o valor da sequencia
      if (iCount++ == iSeq) {
            // reinicia a contagem
            iCount = 1;
            // elimina o numero da lista
            DeleteNode(L, slDel);
      }
}

                Para armazenar a solução da ultima e penúltima posição nos ponteiros pLast e pSecLast, dentro da condicional que elimina os nós incluímos a outra verificação na variável que controla o total de nós na lista.

if (L->uiCount == 1)
      *pLast = ((pND) slDel->pdata)->uPos;
else if (L->uiCount == 2)
      *pSecLast = ((pND) slDel->pdata)->uPos;

                A rotina completa recebe como entrada a quantidade de pessoas e a sequencia de eliminação através da linha de comando para o programa, e irá utilizar os ponteiros pLast e pSecLast para retornar as duas ultimas posições e imprimir o resultado na tela.

BOOL Josephus(int iPerson, int iSeq, int *pLast, int *pSecLast)
{
      SLIST *L;
      int iCount;
      SLINK slQueue, slDel;

      L = CreateLList(CreateData,
                        DeleteData,
                        DuplicatedNode,
                        NodeDataCmp);

      for (iCount = 1; iCount <= iPerson; ++iCount)
            AddNodeAtHead(L, &iCount);

      slQueue = L->slkTail;
      iCount = 1;
      while (L->uiCount) {
            slDel = slQueue;
            slQueue = slQueue->prior;
            if (slQueue == NULL)
                  slQueue = L->slkTail;

            if (iCount++ == iSeq) {
                  iCount = 1;

                  if (L->uiCount == 1)
                        *pLast = ((pND) slDel->pdata)->uPos;
                  else if (L->uiCount == 2)
                        *pSecLast = ((pND) slDel->pdata)->uPos;

                  DeleteNode(L, slDel);
            }
      }
      return (TRUE);
}

int LLDriver(int argc, char *argv[])
{
      int iPerson, iSeq, iLast, iSecLast;

      iPerson = atoi(argv[1]);
      iSeq = atoi(argv[2]);

      Josephus(iPerson, iSeq, &iLast, &iSecLast);
      printf("penultimo: %d\n", iSecLast);
      printf("ultimo:    %d\n", iLast);

      return (EXIT_SUCCESS);
}

                Ao criar e rodar o projeto, o resultado na tela se apresentara da seguinte forma:

C:\Projects\Josephus\Debug>Josephus 41 3

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

1 2 4 5 7 8 10 11 13 14 16 17 19 20 22 23 25 26 28 29 31 32 34 35 37 38 40 41

2 4 7 8 11 13 16 17 20 22 25 26 29 31 34 35 38 40
2 4 8 11 16 17 22 25 29 31 35 38
2 4 11 16 22 25 31 35
2 4 16 22 31 35
4 16 31 35
16 31
16 31
31
31
penultimo: 16
ultimo:    31

C:\Projects\Josephus\Debug>Josephus 10 2
1 2 3 4 5 6 7 8 9 10
1 3 5 7 9
1 5 9
5
5
penultimo: 9
ultimo:    5


Todos os arquivos deste projeto se encontram armazenados no github,  o problema de Josephus permite outro caminho através da permutação fornecendo uma reposta  mais elegante comparada a simples simulação da contagem envolvendo lista encadeada, assunto que voltara a pauta com a postagem de recursividade.