Recursividade com memorização

Estava buscando um problema legal de 
treinamento para a maratona de programação e achei um problema bem
interessante. Ele é interessante pelo motivo de, à primeira vista, parecer bem
simples para quem conhece recursividade. Mas analisando o enunciado melhor
pode-se ver  que uma implementação com
recursão simples não basta para resolvê-lo.

O nome do problema é 3n+1. O link é o seguinte: http://acm.uva.es/problemset/v1/100.html

No enunciado do problema é dado a seguinte:

Para um dado número N, o resultado de uma função recursiva que
resolva o problema varia de acordo com a paridade do número, em caso de ele ser
par, divide-se por dois, em caso de ele ser ímpar, multiplica-se por 3 e
soma-se 1. Esse passo é repetido até o valor retornado ser 1. Como exemplo era
dado o valor 22, onde essa recursão resultava na seguinte sequencia: 22, 11,
34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. Ou seja o resultado é uma
sequência de 16 valores, essa é a sequencia “3n+1” do numero 22. O problema não
parava por aí: a entrada era um range de valores por exemplo 1 a 25 e pedia-se para que
calculasse, para esse range, qual a maior sequencia “3n+1”. E o problema ainda não
parava por aí: essa entrada podia variar de 1 até 1000000, ou seja, para um
algoritmo passar no tempo limite, que é bem curto (3 segundos para todas as
entradas possiveis), não podia fazer todos esses cálculos a cada entrada
diferente.

Para fazer esse algoritmo podemos usar a própria função recursiva mostrada
no problema. Ou seja, ela possui 3 tipos de retorno:

1. o caso de parada para quando o
   valor for o numero 1, retornando o próprio valor 1.
2. quando o valor for um número par a
   função recursiva retorna 1 mais o valor do retorno da própria função
   passando com parametro ele dividido por 2.
3. e quando for impar a função
   retorna 1 mais o valor da função retornado passando-se o triplo do valor
   mais 1.

O truque para o problema é fazer um pré-calculo guardando todos os
valores possíveis em algum lugar, para quando forem requisitados para
comparações não precisar refazer cálculos desnecessários.

Para começar iniciamos com o vetor onde serão armazenados os
valores. Como o máximo de números é 1000000 precisamos de um vetor como
res[1000001] (de zero a 1000000). Se estamos querendo otimizar ao máximo o
algoritmo precisamos ter uma noção de que não podemos deixar esse vetor como um
vetor de inteiros simples, já que ele só vai armazenar a maior sequência
possível. Fazendo os cálculos conseguimos chegar ao valor máximo para essa
sequencia, e não precisamos de um tipo int para isso, basta um tipo short sem
sinal, já que não vamos ter valores negativos no vetor, muitos podem pensar que
isso tudo não é preciso já que apenas estamos lidando com variáveis, mas não,
desde a primeira linha do problema precisamos avaliar a necessidade e a
melhoria o código, já que estamos pensando em valores grandes como 1000000. OK,
agora temos onde armazenar os valores das sequências, vamos para restante. Para
popular o vetor, primeiro podemos já colocar o valor do índice 1, que já
sabemos que é 1, depois basta uma declaração for básica de fazendo tentativas
de colocar o valor do item atual, mas com o auxilio da função recursiva, que
nesse caso vai fazer mais que o cálculo do índice requisitado no parâmetro, ele
vai armazenar os valores no vetor na medida em que for se encontrando com eles,
então a iteração do laço chamador não precisará fazer a chamada para os item
que já tiverem populados.

Como os valores podem sair do range permitido para o vetor, já que
pode-se multiplicar 999999 por 3 em
algum momento do algoritmo, esse caso tem que ser tratado dentro da função.
Como? Simples, caso o valor seja maior que o máximo permitido, a função irá
trabalhar como uma função recursiva padrão, sem armazenar nada, mas continuar
fazendo o cálculo, caso o valor passado esteja dentro do range permitido,
faz-se a função recursiva personalizada, armazenando o dado. Então, para que
possamos tratar essa entrada, temos que permitir a entrada de valores maiores
que um int comum, ou seja um long int. Abaixo está a parte do código que
resolve a recursão com memorização.

unsigned long int max = 1000000; //1000000, não precisa de long int,<br />mas para comparar com valores que são long int sim.<br />unsigned short res[1000001]; <br />//vetor que armazena os dados<br />unsigned short rec(unsigned long int i)<br />{<br />  if(i==1)<br />   return 1;<br />  if(i>max)<br />   return ((i%2)==0)? 1+<br />  rec(i/2) : 1+ rec(i*3 +1);<br />  else<br />  {<br />    res[i] = ((i%2)==0) ? 1 +<br />    rec(i/2) : 1 + rec(i*3 +1);<br />    return res[i];<br />  }<br />}<br />int main()<br />{<br />  []<br />  res[0] = res[1] = 1;<br />  for(i=2;i<=max;i++)<br />  {   <br />    res[i] = (res[i]==0) ? ((i%2)==0)?1+rec(i/2):1+rec(3*i +1)  : res[i] ;<br />  }<br />  []<br />  return 0;<br />}

Eu achei esse problema interessante, já que essa idéia de
memorização pode ser muito bem aplicada no desenvolvimento prático, mas pouca
gente ainda utiliza. Uns porque não são muito familiarizados com recursão,
outros porque fixaram na cabeça que recursão é sinônimo de algoritmo lerdo, o
que é um mito, já que se for usado da forma correta pode até ser a melhor
opção, como é o caso de problemas semelhantes ao acima.