On peut transformer toute fonction récursive en fonction itérative. En effet, le mécanisme qui se cache derrière la récursivité est la pile d'appels qui se souvient du "chemin" d'appels de fonctions qu'on a suivis pour arriver à un endroit du code, et quand une fonction est finie, on revient dans la fonction précédent à l'endroit de l'appel. Mais si au lieu d'exécuter cet appel récursif, on l'ajoute à une pile puis on exécute la fonction sous-jacente depuis une boucle, on obtient une fonction itérative !
Attention, il ne faut pas que l'appel récursif soit utilisé par une opération comme l'addition, ou même un return car ma fonction "enregistre" les appels fait à la fonction elle-même.
Voici mon code avec quelques exemples :
from collections import deque
def iterate(f):
class decorate():
def __init__(self,f):
self.stack = deque()
self.copy = f
def trace(self,*args,**kwargs):
self.stack.append((args,kwargs))
def main(self,*args,**kwargs):
self.copy(*args,**kwargs)
while self.stack:
t = self.stack.popleft()
self.copy(*t[0],**t[1])
dec = decorate(f)
return dec.trace, dec.main
from time import time
def chrono(f,*args,**kwargs):
dbt = time()
f(*args,**kwargs)
print(time()-dbt)
def f(n,acc = 0):
if n>0:
f(n-1,acc+1)
else:
print(acc)
f, main = iterate(f)
chrono(main,2000)
def fibo(n, r=[0]):
if n<2:
r[0]+= 1
else:
fibo(n-1,r)
fibo(n-2,r)
fibo, main = iterate(fibo)
chrono(main,20)
print(r)
Cela n'a d'ailleurs d'intérêt que pour les fonctions récursives terminales, qui peuvent encore plus facilement être transformées en boucles, puisqu'avec par exemple 2 appels récursifs il faudrait exécuter quelque chose comme 2^1000 fois la fonction pour dépasser la limite de Python de 1000 appels récursifs. En plus, c'est beaucoup plus lent que la récursivité. M'enfin, c'est marrant ;)
Mon code est bizarre et pas commenté, donc n'hésitez pas à me poser des questions ![/code]