Recursividade: Que Geringonça é essa?

Escrito por Matheus Rocha.

recursividade

 

Se você trabalha com Desenvolvimento de Softwares ou até mesmo Websites, provavelmente já ouviu o termo em algum momento. Mas, qual a definição luso-brasileira desta palavra? O Google diz que recursividade é:

“[...]Propriedade das regras gramaticais que se podem reaplicar sucessivamente às estruturas resultantes de sua aplicação anterior, explicando assim o conceito teórico de sentença infinitamente longa, no plano da competência linguística.”

Então Recursividade é uma propriedade aplicável, sucessivas vezes às resultantes de sua aplicação anterior. Trazendo a definição do conceito linguístico até a programação, quando construímos uma Função Recursiva, devemos saber que ela será executada N vezes, dependendo de uma condição de saída ou estado anterior do elemento. A forma como este tipo de Função é executada, cria um laço de repetição se o uso de comandos como While, For ou Foreach. Para o nosso exemplo, realizaremos uma Função para encontrar uma Chave em N gavetas. Crie um arquivo chamado index.php (ou o nome que preferir) e coloque-o no diretório do Webserver de sua preferência.

 

No Escopo Principal da nossa rotina temos:

  1. <?
  2. $gavetas = array (
  3.   2 => false,
  4.   3 => false,
  5.   4 => false,
  6.   5 => true,
  7.   6 => false,
  8.   7 => false,
  9.   8 => false,
  10.   9 => false,
  11.   10 => false,
  12. );
  13. ?>

 


Ainda no Escopo Principal, após a declaração do Array de Gavetas, temos:

  1. echo encontraChave($gavetas, 1);

Aqui imprimimos a saída da função recursiva, ao mesmo tempo que a invocamos. O primeiro Parâmetro é o Array que representa todas as gavetas, o segundo representa a primeira posição (ou gaveta) a ser procurada.

 


No Protótipo de nossa Função Recursiva temos:

  1. <?
  2. function encontraChave($gavetas, $gav){
  3.   if ($gavetas[$gav] == false){
  4.    $gav ++;
  5.    return encontraChave($gavetas, $gav);
  6.   }else{
  7.    return $gav;
  8.   }
  9. }
  10. ?>

Cada vez que a Função encontraChave é executada, e a condição $gavetas[$gav] == false é atendida, a variável $gav é incrementada e a Função é chamada novamente, criando uma nova instância e percorrendo o vetor $gavetas por completo, em quanto true não for encontrado. Se $gavetas[$gav] == true, a função retorna $gav, ou seja, a posição onde a chave foi encontrada.

 

Experimente trocar a chave de gaveta, definindo true para a posição desejada. É possível acrescentar quantas gavetas forem necessárias, basta adicionar as linhas de declaração do Vetor:

  1. <?
  2. $gavetas = array (
  3.   1 => false,
  4.   2 => false,
  5.   ...
  6.   ...
  7.   99 => false,
  8.   100 => false,
  9. }
  10. ?>

 

Lembre-se que pelo menos uma posição do Vetor deve conter true, caso contrário a rotina entrará em loop infinito. Várias instâncias da Função são empilhadas, até o momento em que a condição de saída seja atendida. Neste momento, $gav é retornada para TODAS as instâncias já criadas. Com finalidade de teste, troque o trecho de declaração do Array por:

  1. <?
  2. for($g = 0; $g<1000; $g++){
  3.   $gavetas[$g] = false;
  4. }
  5.   
  6. $gavetas[950] = true;
  7. ?>

Aqui atribuímos false para 1000 gavetas e true para a gaveta de número 950. Note que o resultado impresso na tela será o mesmo de antes, só que neste momento, nossa função procurou pela chave em 1000 gavetas, 10 não mais.

 

Espero ter ajudado a entender mais sobre Funções Recursivas e o seu funcionamento. Acompanhe o EscolaWeb e Siga o GreenLabsWeb nas Redes Sociais. Só assim podemos continuar criando conteúdo gratuito e de qualidade, fazendo da Internet um mundo melhor.