7

Em caso afirmativo, como eu poderia, por exemplo, criar uma função recursiva equivalente ao código abaixo?

lista = list(range(1000))
for i in lista:
       print(i)
0

2 Respostas 2

12

Primeiro vou responder o título ("Uma função recursiva pode substituir while e for?") de maneira geral, depois falaremos sobre o código específico da pergunta.


Uma função recursiva pode substituir while e for?

De maneira geral, qualquer algoritmo iterativo pode ser convertido para um recursivo e vice-versa. Mas só porque pode, não quer dizer que você deve fazê-lo. Recursão pode esconder algumas "armadilhas", e mesmo quando parece uma boa ideia, pode ser que a versão iterativa seja melhor.

Um exemplo clássico é o cálculo dos números de Fibonacci, que deve ser um dos mais usados para ensinar recursão. A definição dele é recursiva:

fib(1) = fib(2) = 1
fib(n) = fib(n - 1) + fib(n - 2)

Então é "natural" implementá-lo assim:

def fib(n):
    if n == 1 or n == 2:
        return 1
    return fib(n - 1) + fib(n - 2)

Mas há um problema "oculto", que não é tão óbvio à primeira vista. Se chamarmos fib(10), ocorrerão as seguintes chamadas recursivas:

  • fib(10) chama fib(9) + fib(8)
    • fib(9) chama fib(8) + fib(7)
      • fib(8) chama fib(7) + fib(6)
        • fib(7) chama fib(6) + fib(5)
        • fib(6) chama fib(5) + fib(4)
        • ...
      • fib(7) chama fib(6) + fib(5)
        • fib(6) chama fib(5) + fib(4)
        • fib(5) chama fib(4) + fib(3)
        • ...
    • fib(8) chama fib(7) + fib(6)
      • fib(7) chama fib(6) + fib(5)
        • fib(6) chama fib(5) + fib(4)
        • fib(5) chama fib(4) + fib(3)
        • ...
      • fib(6) chama fib(5) + fib(4)
        • fib(5) chama fib(4) + fib(3)
        • fib(4) chama fib(3) + fib(2)
        • ...

Repare que há várias chamadas repetidas (fib(8) é chamada duas vezes, fib(7) três vezes, fib(6) quatro, etc), ou seja, o mesmo valor pode ser calculado várias e várias vezes, desnecessariamente. A quantidade de chamadas cresce exponencialmente e isso torna este algoritmo bem ineficiente. Claro que você pode usar técnicas de memoization para guardar resultados já computados em um cache (ainda sim, haverá uma chamada para verificar se o resultado está ou não no cache), mas na verdade você só está resolvendo um problema que você mesmo criou ao usar recursão em um caso no qual ela não é a melhor solução. Um algoritmo iterativo como o abaixo:

def fib_iterativo(n):
    a, b = 1, 1
    for i in range(1, n):
        a, b = b, a + b
    return a

É bem mais eficiente: não há chamadas recursivas cuja quantidade cresce exponencialmente e por isso é bem mais rápida.


Outro problema que pode ocorrer é o estouro de pilha. Usando outro exemplo (citado nos comentários), o cálculo do fatorial (outro muito usado para ensinar recursão):

def fat(n):
    if n <= 1:
        return 1
    return n * fat(n - 1)

Se eu chamar fat(5), ele vai chamar 5 * fat(4). Ou seja, ele precisa do retorno de fat(4) para calcular o resultado final. Só que fat(4) vai chamar 4 * fat(3), então ela precisa esperar fat(3) terminar (que por sua vez, chamará 3 * fat(2) e assim por diante).

Existe um limite para toda essa quantidade de chamadas "penduradas" esperando as outras terminarem, e quando este é estourado, ocorre um RecursionError (veja aqui um exemplo).

Já usando uma versão iterativa não ocorre esse problema:

def fat(n):
    res = 1
    for i in range(2, n + 1):
        res *= i
    return res

Pois agora é apenas uma chamada com um loop simples. Além de não estourar a pilha, também é mais rápido.

Então volto a repetir: embora seja possível converter qualquer algoritmo iterativo para recursivo e vice-versa, não quer dizer que você deva necessariamente fazê-lo. Há casos e casos, e para se aprofundar mais, sugiro que leia aqui e aqui (e siga os links que tem nas respostas também).


Sobre o código específico da pergunta

O seu código cria uma lista contendo os números de 0 a 999 e os imprime. Mas o que seria o "equivalente" a este código: uma função que imprime números dentro de um determinado intervalo, ou uma função que recebe uma lista e imprime todos os seus valores? Pode parecer que são a mesma coisa, mas não. Para o primeiro caso, a função recursiva nem precisaria de uma lista:

def imprime_intervalo(inicio, fim):
    if inicio <= fim:
        print(inicio)
        imprime_intervalo(inicio + 1, fim)

import sys
sys.setrecursionlimit(2000)
imprime_intervalo(0, 999)

O detalhe é que nesse caso eu tive que aumentar o limite de recursão usando sys.setrecursionlimit, já que o limite default estava sendo estourado. Esse é o problema do estouro de pilha (já citado acima e também na outra resposta): há um limite bem menor para a quantidade de chamadas recursivas. Ao chamar imprime_intervalo(0, 999), a primeira chamada precisa esperar o retorno de todas as outras 999 chamadas, e todas elas ficam "pendentes" esperando a última chamada terminar. A quantidade de chamadas pendentes é controlada pelo recursion limit, que pode ser consultado por sys.getrecursionlimit.

Por isso, o mesmo problema ocorre se tivermos um algoritmo recursivo para imprimir os valores de uma lista:

def imprime_lista(lista, i=0):
    if i < len(lista):
        print(lista[i])
        imprime_lista(lista, i + 1)

imprime_lista([ 'a', 'b', 'c' ])

import sys
# para uma lista com mais de 1000 elementos, precisa aumentar o limite de recursão
sys.setrecursionlimit(2000)
imprime_lista(list(range(1000)))

Existe ainda uma outra alternativa, que é imprimir o primeiro elemento da lista e chamar a função recursiva passando o restante da lista (uma sub-lista contendo do segundo elemento em diante):

def imprime_lista(lista):
    if lista: # se a lista não é vazia
        print(lista[0])
        imprime_lista(lista[1:])

imprime_lista([ 'a', 'b', 'c' ])

import sys
# para uma lista com mais de 1000 elementos, precisa aumentar o limite de recursão
sys.setrecursionlimit(2000)
imprime_lista(list(range(1000)))

Mas além de ter o problema do estouro de pilha, essa versão é ainda mais ineficiente, por ter que criar várias sub-listas (uma nova sub-lista a cada chamada recursiva).


Então, mais um vez reforço: só porque é possível converter um algoritmo iterativo para um recursivo, não quer dizer que você deva fazê-lo.

2
  • 2
    Nota que alguns problemas de dividir e conquistar são bem mais fáceis de dar manutenção com versão recursiva. Vou procurar editar essa resposta e postar a versão iterativa pra mostrar o como fica bagunçado Commented 9/03/2020 às 18:55
  • @JeffersonQuesado Ah sim, tem casos e casos. Na resposta eu foquei nos casos em que a versão recursiva é pior, mas com certeza tem casos que é o contrário
    – hkotsubo
    Commented 9/03/2020 às 19:03
8

Se implementares recursividade para valores elevados, com mil por exemplo vai retornar um erro:

recursion error maximum recursion depth exceeded

É uma proteção contra o stack overflow, sim. O Python (ou melhor, a implementação do CPython) não otimiza a recursão, ​​e a recursão desenfreada causa este problema. Você pode verificar o limite permitido pela recursão com sys.getrecursionlimit e alterar o limite de recursão com sys.setrecursionlimit, mas fazer isso é perigoso - o limite padrão é um pouco conservador, mas os quadros de pilha Python podem ser bastante grandes. Python não é uma linguagem funcional e a recursividade não é uma técnica particularmente eficiente. Reescrever o algoritmo iterativamente, geralmente é uma ideia melhor.

Contudo. Tens aqui um exemplo:

list = [1,2,3,4,5]

def load(i, arr):
  if i < len(arr):
    print(arr[i])
    i += 1
    load(i, arr)

load(0, list)
4
  • E em que tipo de caso recursão é uma técnica viável?
    – Luan
    Commented 5/03/2020 às 21:21
  • 1
    Tens aqui ime.usp.br/~leo/mac2166/2017-1/introducao_recursividade.html uma explicação detalhada. Os exemplos tipicos de recursividade, o calculo do fatorial, calcular combinações possível de moedas. entre outros. Commented 5/03/2020 às 21:32
  • 1
    @Luan pt.stackoverflow.com/q/21551/112052
    – hkotsubo
    Commented 5/03/2020 às 22:49
  • Se achar uma linguagem com "tail recursion optimization", não estoura a pilha. Basta que a chamada recursiva seja a última coisa que a função faz. Em tese a especificação do Javascript prevê isso, mas parece que nenhuma implementação realmente aplicou.
    – epx
    Commented 6/03/2020 às 12:23

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .