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)
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).
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.
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)