Hoje me deparei com um problema bem interessante no codefights:

Screen-Shot-2018-03-19-at-22.22.07

O algorítmo que fiz para resolvê-lo foi:

  1. Se n for igual a 1, retorne 1;
  2. Se n for maior que 1, pegue o resultado anterior e some a 4 * (n - 1);
    1. Exemplo: o valor para 1-interesting é 1, para 2-interesting é 1 + 4 * (2 - 1), que é 5;

Minha primeira abordagem foi utilizar recursão, como mostra o código abaixo:

Entretanto, ao inserir um valor muito alto eu recebi a exceção: RecursionError: maximum recursion depth exceeded in comparison.

Para entender o erro, considere o código abaixo:

O Python criará uma pilha de chamadas mais ou menos assim:
hola()
ola()
e por fim...
hello()

Quando a capacidade máxima dessa pilha é atingida, uma RecursionError é levantada. Nota: este valor pode ser alterado com o código abaixo:

Beeem a grosso modo, em algumas linguagens de programação uma maneira de lidar com este problema é utilizando Tail Recursion, onde a última instrução de uma função é uma chamada à mesma; nesses casos o compilador fica responsável pela otimização da pilha de chamadas de modo a não permitir que esse tipo de exceção seja levantada. Contudo, entretanto, todavia, Guido Van Rossum disse que não tem planos de implementar esse tipo de otimização no Python.

A maneira que resolvi este problema foi não usar recursão e salvar o estado da variável result no escopo do método até o while atingir a condição de parada:

Até a próxima! :)