Recursão por Referencia

• A recursão é uma técnica que define um problema em termos de uma ou mais versões menores deste mesmo problema. Esta ferramenta pode ser utilizada sempre que for possível expressar a solução de um problema em função do próprio problema;

• Para se codificar programas de modo recursivo usa-se um procedimento ou sub-rotina, que permite dar um nome a um comando, o qual pode chamar a si próprio. Esta chamada pode ser diretamente recursiva, quando o procedimento P contiver uma referência explícita a si próprio, ou indiretamente recursiva, quando o procedimento P contiver uma referência a outro procedimento Q, que por sua vez contém uma referência direta ou indireta a P.

• Assim, vamos relembrar o exemplo do fatorial recursivo:

  #include <stdio.h>
  
  int fatorial( int n )
  {
      if ( (n == 1) || (n == 0) ){
  			return 1;
  		}
      else { 
  			return fatorial( n - 1 ) * n;
  		}
  }
  
  void main(){
      int n = 5;
      printf("Fatorial = %d\\n", fatorial( n ) );
  }
  

• Caso seja necessário transformar o seguinte código para uma estrutura de referencia, onde o valor referenciado deve mudar, a primeira impressão seria modificar o código para o seguinte contexto:

  #include <stdio.h>
  
  int fatorialReferenciaErrado( int *n )
  {
      if ( ( *n == 1 ) || ( *n == 0 ) ){
  			return 1;
  		}
      else { 
  			return fatorialReferenciaErrado( *n - 1 ) * n;
  		}
  }
  
  void main(){
      int n = 5;
      printf("Fatorial = %d\\n", fatorialReferenciaErrado( &n ) );
  }
  

• No entanto, o código anterior está incorreto, pois se está recebendo por referência e precisa alterar a própria referência, a função não retornará o resultado, mas sim deve atribuir o resultado no próprio ponteiro. Desta forma, o código deve ser remodelado para que corretamente atribuir o valor a referencia:

  void fatorialReferenciaCorreto( int *n ) {
      int temp, resultado = 1;
  
      if ( *n > 1 ) {
          temp = *n - 1;
          fatorialReferenciaCorreto( &temp );
          resultado = ( *n ) * temp;
      }
      *n = resultado;
  }
  
  void main()
  {
  	int n = 5;
  	fatorialReferenciaCorreto( &n );
  
  	printf("Fatorial = %d", n);
  }
  
  

• Assim, ao fazer o exemplo, será exibido o valor 120, referente ao valor de 5! calculado. A ideia do código é:

  • Define as variáveis temp, que armazenará o resultado de fatorial(n-1) se necessário, e resultado, que armazenará o resultado final;
  • Se o valor de n for maior que 1, calcula o fatorial de maneira recursiva;
  • Define o valor de temp como sendo o valor de n decrementado em 1;
  • Chama a função de fatorial passando a referência de temp, assim temp possuirá o valor do fatorial de n-1;
  • Define o valor do resultado como o valor de n multiplicado pelo valor de temp;
  • Atualiza o valor da referência com o valor de resultado;

• O desenvolvimento de uma solução recursiva sem o algoritmo nem sempre é fácil. Normalmente, não há porque propor uma solução recursiva, entretanto, para alguns problemas a solução recursiva é mais elegante, sendo que existem problemas que são recursivos já na sua definição, para estes, a solução recursiva é mais natural.

Recursão de Cauda

• A recursão de cauda é uma técnica de recursão que faz menos uso de memória durante o processo de empilhamento, o que a torna mais rápida que a recursão comum. Em uma recursão comum, a cada chamada recursiva realizada, é necessário guardar a posição do código onde foi feita a chamada para que continue a partir dali assim que receber o resultado. Em uma recursão de cauda, não é necessário guardar a posição onde foi feita a chamada, visto que a chamada é a última operação realizada pela função.

• Recursão de cauda é um conceito em programação em que a chamada recursiva é a última ação executada em uma função. Isso significa que, após a chamada recursiva, não há nenhuma operação adicional a ser realizada. Isso contrasta com a recursão normal, onde a chamada recursiva é seguida por alguma operação de pós-processamento.

• A principal vantagem da recursão de cauda é que ela pode ser otimizada pelo compilador ou interpretador, resultando em um uso mais eficiente de recursos, como memória e tempo de execução. A otimização de cauda é uma técnica que permite ao compilador transformar recursões de cauda em loops, eliminando a necessidade de manter uma pilha de chamadas.

• A otimização de cauda é uma técnica importante em linguagens funcionais e em algumas linguagens de programação imperativas modernas que suportam recursão de cauda, como algumas implementações de C e C++. No entanto, nem todas as linguagens e compiladores oferecem suporte automático para otimização de cauda, portanto, é importante entender como funciona e quando aplicá-la, especialmente em situações que envolvem recursões profundas.

• Exemplo: o fatorial de um inteiro n não-negativo, escrito n!, é o produto n * (n -1) * (n - 2) * … * 1. O cálculo recursivo do fatorial de n pode ser feito como a seguir:

  int fatorial( int n )
  {
      if ( (n == 1) || (n == 0) ){
  			return 1;
  		}
      else { 
  			return fatorial( n - 1 ) * n;
  		}
  }
  

• Note que após receber o resultado da chamada recursiva (linha 6) ele deve ser multiplicado por n. Daí a necessidade de uma variável para guardar a posição onde foi feita a chamada recursiva. Uma recursão de cauda é aquela onde a chamada recursiva é a última operação a ser realizada pela função recursiva. A função fatorialCauda() a seguir implementa a recursão de cauda para o fatorial:

  int fatorialParcial( int num, int parcial )
  {
  	if ( num == 1 )
  		return parcial;
  	else
  		return fatorialParcial( (num - 1) , (parcial * num) );
  }
  
  int fatorialCauda( int num )
  {
  	return fatorialParcial( num, 1 );
  }
  

• Nesse caso, o conceito da avaliação do caso base é diferente. Embora exista uma checagem deste caso na função fatorialParcial(), o problema inicial não é reduzido até este ponto para que então a função retorne a resposta deste caso (ou seja, fatorial(1) = 1). O que acontece é uma transcrição direta de um cálculo iterativo: passa-se inicialmente o valor parcial 1 para a função fatorialParcial() e ela “atualiza” este valor a cada chamada recursiva, multiplicando o cálculo parcial do fatorial por n, n – 1, n – 2, …, até o “caso base”. Neste ponto, o valor do fatorial já foi calculado e é apenas retornado.

• Exemplificação: Seqüência de Fibonacci

• Cada termo resulta da adição dos dois que o antecedem (Un = Un-1 + Un-2) originando assim os números 0; 1; 1; 2; 3; 5; 8; 13; 21 e por aí em diante. Os números desta série têm muitas propriedades e aplicações interessantes, por exemplo na botânica, no desenvolvimento de plantas (arranjo das folhas), e na genética, na produção de coelhos.

  

  int fibonacci( int n )
  {
  	if (n < 2)
  		return n;
  	else 
  		return fibonacci( n - 1 ) + fibonacci( n - 2 ) ;
  }
  
  void main()
  {
  	int n;
  	scanf("%d", &n);
  	printf("%d", fibonacci( n ) );
  }
  

• Esquematização de fibonacci(4):