Removendo recursão no Python

Olá Habr! Apresento a você a tradução do artigo "Removendo uma recursão no Python, parte 1", de Eric Lippert.

Nos últimos 20 anos, admirei a simplicidade e o poder do Python, embora nunca tenha realmente trabalhado com ele ou estudado em detalhes.

Recentemente, olhei atentamente para ele - e acabou sendo uma linguagem muito boa.

Uma pergunta recente no StackOverflow me fez pensar em como converter um algoritmo recursivo em um iterativo, e o Python era uma linguagem muito boa para isso.
O problema que o autor da pergunta encontrou foi o seguinte:

• O jogador está em uma célula arbitrária em um campo numerado;
• O objetivo é retornar à célula número 1;
• Se o jogador estiver no mesmo quadrado, ele paga uma moeda e vai até a célula número 1;
• Se o jogador estiver em um quadrado ímpar, ele pode pagar 5 moedas e ir diretamente para o primeiro quadrado ou pagar uma moeda e dar um passo para o número 1 - em um quadrado par.

A questão é: qual é a menor quantidade de moedas que você precisa pagar para retornar da célula atual para a primeira.

A tarefa tem uma solução recursiva óbvia:

def cost(s): if s <= 1: return 0 if s % 2 == 0: return 1 + cost(s // 2) return min(1 + cost(s - 1), 5) 

No entanto, esse programa travou, atingindo a profundidade máxima de recursão, provavelmente devido ao fato de o autor da pergunta ter experimentado números muito grandes.
Portanto, surge a pergunta: como transformar um algoritmo recursivo em iterativo em Python?

Antes de começar, quero observar que é claro que existem soluções mais rápidas para esse problema específico, por si só não é muito interessante.

Em vez disso, essa tarefa serviu apenas como ponto de partida na questão de como, no caso geral, livrar-se de uma única chamada recursiva em um programa Python.

O ponto é que você pode converter qualquer método recursivo simples e se livrar da recursão, e este é apenas um exemplo que estava à mão.

A técnica que mostrarei, é claro, não corresponde exatamente à maneira como o Python é escrito, provavelmente uma solução no estilo Python usaria geradores ou outros recursos da linguagem.

O que quero mostrar aqui é como se livrar da recursão usando uma sequência de transformações pequenas e seguras, levando a função a uma forma em que é fácil substituir a recursão por uma iteração.

Para começar, vamos ver como levar o programa para este formulário.

Na primeira etapa de nossa conversão, desejo que os cálculos realizados antes da chamada recursiva sejam reduzidos ao cálculo do argumento e que os cálculos, após a chamada recursiva, sejam executados em um método separado que aceite o resultado da chamada recursiva.

 def add_one(n): return n + 1 def get_min(n): return min(n + 1, 5) def cost(s): if s <= 1: return 0 if s % 2 == 0: argument = s // 2 result = cost(argument) return add_one(result) argument = s - 1 result = cost(argument) return get_min(result) 

O segundo passo que quero fazer é o cálculo do argumento em uma função separada:

 # ... def get_argument(s): if s % 2 == 0: return s // 2 return s - 1 def cost(s): if s <= 1: return 0 argument = get_argument(s) result = cost(argument) if s % 2 == 0: return add_one(result) return get_min(result) 

Na terceira etapa, desejo adicionar uma função auxiliar que selecione a função de continuação chamada após retornar da recursão.

Observe que a função auxiliar retorna uma função.

 #... def get_after(s): if s % 2 == 0: return add_one return get_min def cost(s): if s <= 1: return 0 argument = get_argument(s) after = get_after(s) # after  ! result = cost(argument) return after(result) 

Agora, escrevemos de uma forma mais geral e concisa:

 #... def is_base_case(s): return s <= 1 def base_case_value(s): return 0 def cost(s): if is_base_case(s): return base_case_value(s) argument = get_argument(s) after = get_after(s) return after(cost(argument)) 

Pode-se observar que cada mudança realizada retinha o significado do programa.

Agora, a verificação da paridade do número é realizada duas vezes, embora antes das alterações houvesse uma verificação.

Se quisermos, podemos resolver esse problema combinando duas funções auxiliares em uma que retorne uma tupla.

Mas não vamos nos preocupar com isso como parte desta tarefa.

Reduzimos nosso método recursivo para a forma mais geral.

• No caso base:
  
  • calcule o valor a ser retornado;
  • devolva.
• Em um caso não básico:
  
  • computar o argumento de recursão;
  • faça uma chamada recursiva;
  • calcular o valor de retorno;
  • devolva.

Algo importante que você precisa prestar atenção nesta etapa é que after não deve conter chamadas de cost .

O método que mostro aqui remove uma única chamada recursiva.

Se você tem 2 ou mais recursões, precisamos de uma solução diferente.

Depois que trouxemos nosso algoritmo recursivo para esse formulário, já é fácil convertê-lo em iterativo.

O truque é imaginar o que acontece em um programa recursivo.

Como fazemos uma descida recursiva: chamamos get_argument antes da chamada recursiva e chamamos a função after após retornar da recursão.

Ou seja, todas as chamadas para get_argument ocorrem antes de todas as chamadas para depois .
Portanto, podemos converter isso em 2 ciclos: o primeiro chama get_argument e forma uma lista de funções posteriores , e o segundo chama todas as funções posteriores :

 #... def cost(s): #     "after".    #       # ,    . afters = [ ] while not is_base_case(s): argument = get_argument(s) after = get_after(s) afters.append(after) s = argument #       "after" : result = base_case_value(s) while len(afters) != 0: after = afters.pop() result = after(result) return result 

Não há mais recursão!

Parece mágica, mas tudo o que fazemos aqui é o mesmo que a versão recursiva do programa e na mesma ordem.

Este exemplo reflete o pensamento que muitas vezes repito sobre a pilha de chamadas: seu objetivo é comunicar o que acontecerá a seguir, e não o que já aconteceu!

A única informação útil na pilha de chamadas na versão recursiva do programa é qual é o valor posterior , pois essa função é chamada a seguir e tudo o mais na pilha não é importante.

Em vez de usar a pilha de chamadas como uma maneira ineficiente e complicada de armazenar a pilha posterior , podemos simplesmente armazenar a pilha de funções posteriores .

Da próxima vez , veremos uma maneira mais complexa de remover a recursão no Python.