Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #59 da revista programar. Faz já o download aqui!

PsySc0rpi0n

Recursividade de funções

Mensagens Recomendadas

PsySc0rpi0n    8
PsySc0rpi0n

Boas...

A propósito de árvores de pesquisa binária, estou a tentar perceber/seguir o código de uma função recursiva.

Tomemos como exemplo a seguinte função:

int GetNodeHeight ( bstNode *node ) {
   int height_left = 0;
   int height_right = 0;

   if( node->left )
       height_left = GetNodeHeight ( node->left );
   if( node->right )
       height_right = GetNodeHeight ( node->right );

   return height_right > height_left ? ++height_right : ++height_left;
}

Não vai ser fácil tentar explicar, mas vou tentar.

Então imaginemos que temos um conjunto de endereços de memória que serão passados para esta função. Por exemplo:

Caso 1: estes endereços serão usados no "if (node->left)"

100

700

800

NULL

Caso 2: estes endereços serão usados no "if (node->right)"

100

700

900

1000

1100

NULL

Portanto quando o endereço 100 é enviado para a função, o "if (node->left)" testa o endereço 100, como não é NULL, executa a linha seguinte. A linha seguinte, chama a mesma função e envia o endereço 700. O "if (node->left)" é executado novamente ,portanto "if (700)", como também não é NULL, a linha seguinte é executada de novo chamando a mesma função com o endereço 800. O "if (node->left)" é executado como "if (NULL)" e neste momento a função salta para o return e vai executar o operador ternário, fazendo a verificação "height_right > height_left", neste momento, 0 > 0, e como é falso, a variável "height_left" é incrementada, ficando com o valor de 1. Este valor 1 vai ser guardado em height_left após este retorno.

Agora, ignorando o "if( node->right )", a função volta para onde estava antes, ou seja, para a linha do if( node->left ) e vai saltar imediatamente de novo para o return com o operador ternário e vai verificar de novo a condição "height_right > height_left", 0 > 1 que é falsa de novo e volta a incrementar a variável heigh_left e que será guardada no height_left que se encontra dentro do if, ficando agora com o valor 2.

Não sei se esta explicação está correcta mas como o resultado esperado é 2, e como ainda não andei "para trás" tantas vezes quantas as que chamei a função recursivamente, estou num impasse. Porque antes de andar para trás quantas vezes andei para a frente, já estou com o valor esperado!

Como é que eu vou pensar nisto de forma a acertar com a recursividade da função?

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Flinger    50
Flinger

Diz-me uma coisa, se só tiveres o nodo raiz (sem branches), qual é suposto ser o tamanho da àrvore?

Se for suposto ser 1 então a tua função está correcta.

Se for 0 o que tu tens é de deixar de considerar um nodo sem branches como tamanho 1, logo deixas de incrementar no return, mas incrementas apenas na existência de ramos:

int GetNodeHeight ( bstNode *node ) {
int height_left = 0;
int height_right = 0;

if( node->left )
	height_left = 1 + GetNodeHeight ( node->left );
if( node->right )
	height_right = 1 + GetNodeHeight ( node->right );

return height_right > height_left ? height_right : height_left;
}

Creio que assim dá, ora testa lá.

Editado por Flinger

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
PsySc0rpi0n    8
PsySc0rpi0n

Diz-me uma coisa, se só tiveres o nodo raiz (sem branches), qual é suposto ser o tamanho da àrvore?

Se for suposto ser 1 então a tua função está correcta.

Se for 0 o que tu tens é de deixar de considerar um nodo sem branches como tamanho 1, logo deixas de incrementar no return, mas incrementas apenas na existência de ramos:

int GetNodeHeight ( bstNode *node ) {
int height_left = 0;
int height_right = 0;

if( node->left )
	height_left = 1 + GetNodeHeight ( node->left );
if( node->right )
	height_right = 1 + GetNodeHeight ( node->right );

return height_right > height_left ? height_right : height_left;
}

Creio que assim dá, ora testa lá.

Sim, o nó root sem branches, daria 1.

Mas a minha questão nem é essa! É se a descrição que fiz do funcionamento da recursividade da função está correcta ou se falhei em algum lado!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Flinger    50
Flinger

Essa tua descrição está um bocado confusa...

Deixa lá ver se te consigo explicar. Tu tens a seguinte àrvore:

100
/ \
700 900
/ \
800 1000

Em que os inteiros são os endereços de memória (para seguir o teu exemplo)

Então a tua função recebe na primeira chamada o valor 100. Ora o primeiro if não testa 100 (aliás se passares NULL à função o programa rebenta), testa 100->left que, neste caso será 700 (o endereço do nó à esquerda de 100). Como ele existe, invoca a função com o valor 700.

if (700->left) , neste caso 800, então invoca a função com o valor 800.

if (800->left) neste caso não existe elemento à esquerda, logo 800->left=NULL.

if (800->right) também não existe elemento à direita.

então retorna ++0, logo 1;

if (700->right), não existe elemento à direita de 700;

logo retorna ++height_left, ou seja 2.

if (100->right), que é o elemento 900, logo invoca a função com 900

... and so on

retorna ++height_left logo 3.

Tás a ver o filme, ou queres que termine o branch da direita?

Editado por Flinger

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
PsySc0rpi0n    8
PsySc0rpi0n

Pois, eu acho que fiz o raciocínio correcto, mas supostamtente o resultado teria que ser 2. Estamos a analisar a "height" do nó 100. Com a "height" se define como o caminho mais longo desde o nó até ao ultimo nó do fundo, neste caso teria que ser dois. Ou seja, para além do nó root, temos 2 dós até ao fundo da árvore!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Flinger    50
Flinger

Mas a tua função considera a raíz como valendo 1, logo o total da àrvore dá 3. Está a contar o número de níveis, por assim dizer, e vês pela àrvore que tens 3.

É como contares a altura de um prédio, em andares. Contas o rés do chão?

Na função que eu escrevi, só contas as ligações, ou os lanços de escadas, por assim dizer.

Já lá vai muito tempo, não me recordo se a altura considera ou não a raíz, por isso expus os 2 casos.

Editado por Flinger

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
PsySc0rpi0n    8
PsySc0rpi0n

Mas a tua função considera a raíz como valendo 1, logo o total da àrvore dá 3. Está a contar o número de níveis, por assim dizer, e vês pela àrvore que tens 3.

É como contares a altura de um prédio, em andares. Contas o rés do chão?

Na função que eu escrevi, só contas as ligações, ou os lanços de escadas, por assim dizer.

Já lá vai muito tempo, não me recordo se a altura considera ou não a raíz, por isso expus os 2 casos.

Mais especificamente, estamos a contar a altura de um nó, independentemente, se é o root ou não. Portanto, se eu quiser saber a altura do nó root, esse dar-me-á 2, pois, a baixo dele, há no máximo 2 nós.

Eu percebi o teu raciocínio quando colocaste o + 1. Mas queria ter a certeza que a minha explicação estava correcta sobre a recursividade de funções. A minha dificuldade estava em conseguir "keep track" das vezes que tinha que andar para trás nas chamadas da própria função. O que tu fizeste foi bom, ou seja, fazeres tipo em pseudo-código identado! Ajuda a não nos perdermos quando chamamos a função várias vezes e para sabermos quando devemos parar de andar para trás. Não sei se me estou a fazer entender!

Quando se chama a função por exemplo 3 vezes, é como se estivéssemos a descer 3 níveis na função. E depois depois que subir os mesmos 3 níveis para ficar "à superfície"... E é neste vir à superfície que me estou/estava a perder!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo    1153
HappyHippyHippo

Mais especificamente, estamos a contar a altura de um nó, independentemente, se é o root ou não. Portanto, se eu quiser saber a altura do nó root, esse dar-me-á 2, pois, a baixo dele, há no máximo 2 nós.

essa explicação está errada, e como exemplo, vou dar uma árvore em que debaixo de um nó tens 2 nós mas a áltura é 1:

    A
   / \
  B   C

já agora, a raiz da árvore não conta para a chamada "altura de uma árvore".

exemplo de uma árvore (não balanceada) com altura 3:

    A
   / \
  B   C
 /     \
D       E
       / \
      F   G

Editado por HappyHippyHippo

IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
PsySc0rpi0n    8
PsySc0rpi0n

essa explicação está errada, e como exemplo, vou dar uma árvore em que debaixo de um nó tens 2 nós mas a áltura é 1:

    A
   / \
  B   C

já agora, a raiz da árvore não conta para a chamada "altura de uma árvore".

exemplo de uma árvore (não balanceada) com altura 3:

    A
   / \
  B   C
 /     \
D       E
       / \
      F   G

Pois, a escolha das minhas palavras não foi a melhor!

A altura da árvore é o número de nós da "root" até às chamadas "leafs" que são nós sem ramificações, escolhendo o caminho mais longo possível!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
PsySc0rpi0n    8
PsySc0rpi0n

Então o código se calhar, para dar certo, não terá que ser assim:

int GetNodeHeight ( bstNode *node ) {
  int height_left = 0;
  int height_right = 0;

  if( node->left )
  height_left = GetNodeHeight ( node->left );
  if( node->right )
  height_right = GetNodeHeight ( node->right );

  return height_right > height_left ? height_right - 1 : height_left - 1;
}

Editado por PsySc0rpi0n

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
PsySc0rpi0n    8
PsySc0rpi0n

não

faltam duas coisas fundamentais no processo recursivo :

- termo de paragem

- incremento

O termo de paragem não é quando os 'if' encontram NULL???

Relativamente ao increment, copiei o code do Flinger em vez de copier o meu.

int GetNodeHeight ( bstNode *node ) {
  int height_left = 0;
  int height_right = 0;

  if( node->left )
         height_left = GetNodeHeight ( node->left );
  if( node->right )
         height_right = GetNodeHeight ( node->right );

  return height_right > height_left ? ++height_right - 1 : ++height_left - 1;
}

Editado por PsySc0rpi0n

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo    1153
HappyHippyHippo

prontos ... andas às voltas disso à demasiado tempo

int GetNodeHeight ( bstNode *node ) {
  if ( !node ) return 0; // <-- termo de paragem
  int left = GetNodeHeight( node->left ), right = GetNodeHeight( node->right );
  return 1 + (left > right ? left : right); // <-- incremento
}

IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo    1153
HappyHippyHippo

vamos ver um exemplo:

    A
   / \
  B   C
 /     \
D       E
       / \
      F   G

agora o código que apresentei:

int GetNodeHeight ( bstNode *node ) {
 if ( !node )
   return 0;

 int left = GetNodeHeight( node->left ),
     right = GetNodeHeight( node->right );

 return 1 + (left > right ? left : right);
}

agora vamos chamar a função sobre a raiz da árvore:

GetNodeHeight(raiz); // raiz == A

   // A != NULL
   GetNodeHeight(node->left);   // A->B
       // B != NULL
       GetNodeHeight(node->left);   // B->D
           // D != NULL
           GetNodeHeight(node->left);   // D->NULL
               // NULL == NULL
               return 0;
           GetNodeHeight(node->right);  // D->NULL
               // NULL == NULL
               return 0;
           return max(0, 0) + 1;    // = 1
       GetNodeHeight(node->right);  // B->NULL
           // NULL == NULL
           return 0;
       return max(1, 0) + 1;    // = 2
   GetNodeHeight(node->right);  // A->C
       // C != NULL
       GetNodeHeight(node->left);   // C->NULL
           // NULL == NULL
           return 0;
       GetNodeHeight(node->right);  // C->E
           // E != NULL
           GetNodeHeight(node->left);   // E->F
               // F != NULL
               GetNodeHeight(node->left);   // F->NULL
                   // NULL == NULL
                   return 0;
               GetNodeHeight(node->right);  // F->NULL
                   // NULL == NULL
                   return 0;
               return max(0, 0) + 1;    // = 1
           GetNodeHeight(node->right);  // E->G
               // G != NULL
               GetNodeHeight(node->left);   // G->NULL
                   // NULL == NULL
                   return 0;
               GetNodeHeight(node->right);  // G->NULL
                   // NULL == NULL
                   return 0;
               return max(0, 0) + 1;    // = 1
           return max(1, 1) + 1;    // = 2
       return max(0, 2) + 1;    // = 3
   return max(2, 3) + 1;    // = 4

// --------------------------------------------------------

edit : update do código para contabilizar o número de arcos

int GetNodeHeight ( bstNode *node ) {
 if ( !node )                               // termo de paragem
   return 0;                                // retornar zero

 int left = GetNodeHeight( node->left ),    // calcular a altura do ramo da esquerda
     right = GetNodeHeight( node->right ),  // calcular a altura do ramo da direita
     max = (left > right ? left : right);   // obter a maior altura

 return max ? max + 1 : 0;                  // retornar a maior altura mais o arco para esse ramo,
                                            // caso a maior altura for zero, quer dizer que não existem
                                            // arcos/ramos no nó iterado
}

Editado por HappyHippyHippo

IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.