Introdução a Recursão

Publicado por Rafael Siqueira Telles Vieira 09/03/2007

[ Hits: 5.939 ]

Homepage: http://www.lia.ufc.br/~rafaelstv/

Download rec.cpp




Um exemplo simples de recursão. Espero que sirva de base para ajudar a compreeender o uso do algoritmo de quicksort e busca binária.

Neste exemplo eu preencho um vetor com 11 posições(0 à 11) que armazena ponteiros para pontos, sempre visitando a posição média do vetor e em seguida e média da média e assim por diante.

Enquanto isso, vou armazenando os pontos médios dos pontos armazenados nas extremidades.

  



Esconder código-fonte

#include <iostream.h>

struct ponto{
    float x;
    float y;
    };

void X(ponto** p, ponto* p1, ponto* p2, int i, int f){

int novapos;

if ((i+f) % 2 == 1){

    novapos = ((i+f)+1)/2;
} else {
    novapos = (i+f)/2;

}

if (p[novapos]==NULL)   {

    ponto *np = (ponto*) malloc(sizeof(ponto*));
    (*np).x = ((*p1).x + (*p2).x)/2;
    (*np).y = ((*p1).y + (*p2).y)/2;
    
    p[novapos] = np;

    X(p, p1, np, i, novapos);
    X(p, np, p2, novapos, f);

    }
}

int main()
{
    ponto* pini = (ponto*) malloc(sizeof(ponto*));
    ponto* pfim = (ponto*) malloc(sizeof(ponto*));
    (*pini).x = 0;
    (*pini).y = 0;
    (*pfim).x = 10;
    (*pfim).y = 10;

    ponto **p = (ponto**) malloc(11*sizeof(ponto*));

    p[0] = pini;
    p[10] = pfim;   

    X(p, pini, pfim, 0, 10);

// Imprime os resultados no Console

    for (int i=0;i<=10;i++){      
       cout<<"-------"<<endl;
       cout<<i<<endl;
   cout<<"x:"<<(*p[i]).x<<endl;
       cout<<"y:"<<(*p[i]).y<<endl;
       cout<<"-------"<<endl;
    }   
    return 0;
}

Scripts recomendados

Retorna o tempo ocioso em uma sessão do X

Algoritmo estatístico para cálculo de PI em C

Pilha

Run Length Encoding

Pilha estática em C


  

Comentários

Nenhum comentário foi encontrado.


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner
Linux banner

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts