Python Tips - Playing with recursion

Aujourd'hui nous allons découvrir le concept de récursion ou de récursivité, avec Python!

"Bah c'est quoi du coup ? "

Wikipedia est notre ami.

Récursion:
La récursivité est une démarche qui fait référence à l'objet même de la démarche à un moment du processus. En d'autres termes, c'est une démarche dont la description mène à la répétition d'une même règle.

Ici ce qui nous intéresse c'est la récursion d'un algorithme ou plus simple de l'éxécution d'une fonction.

Par exemple, la suite de Fibonacci est application directe du concept de récursion.

On peut la retranscrire en une fonction de cette façon

def Fibonacci(n): 
    if n<0: 
        print("Incorrect input") 
    # First Fibonacci number is 0 
    elif n==1: 
        return 0
    # Second Fibonacci number is 1 
    elif n==2: 
        return 1
    else: 
        return Fibonacci(n-1)+Fibonacci(n-2) 

Exécution

>>>print(Fibonacci(9))
21

"Bon ... génial, mais sinon ça sert à quoi ?"

On peut s'en servir dans des tas d'applications, mais si on peut choisir une solution sans récursion, il vaut mieux l'utiliser. Cette solution sans récursion prendra sans doute moins de temps d'éxécution et moins de mémoire.

"Bof du coup ? ."

Alors il y a des cas ou la récursion est obligatoire, et dans ces cas précis, il vaut mieux savoir bien s'en servir.

MAIS on peut faire des trucs très sympa aussi :

Comme ça

import turtle

def tree(branchLen,t):
    if branchLen > 20:
        t.forward(branchLen)
        t.right(20)
        tree(branchLen-15,t)
        t.left(40)
        tree(branchLen-15,t)
        t.right(20)
        t.backward(branchLen)

def main():
    t = turtle.Turtle()
    myWin = turtle.Screen()
    myWin.bgcolor('black')
    t.speed(0)
    t.left(90)
    t.up()
    t.backward(100)
    t.down()
    t.color("white")
    tree(100,t)
    myWin.exitonclick()

main()

Et ça rend ceci:

Joli non ?
On peut me faire mieux :

import turtle
from random import choice
def tree(branchLen,t):
    COLORS=['red',
            'blue',
            'yellow',
            'green',
            'aquamarine2',
            'bisque',
            'blue2',
            'CadetBlue2',
            'DarkOrange3',
            'firebrick1',
            'ForestGreen',
            'goldenrod2',
            'AliceBlue',
            'azure2',
            'beige']
    t.color(choice(COLORS))

    if branchLen > 20:
        t.forward(branchLen)
        t.right(20)
        tree(branchLen-15,t)
        t.left(40)
        tree(branchLen-15,t)
        t.right(20)
        t.backward(branchLen)
def main():
    t = turtle.Turtle()
    myWin = turtle.Screen()
    myWin.bgcolor('black')
    t.speed(0)
    t.left(90)
    t.up()
    t.backward(100)
    t.down()
    t.color("white")
    tree(100,t)
    myWin.exitonclick()
main()

---

Avec python on ne peut pas faire de la récursion à l'infini, l'interpréteur va nous en empêcher en utilisant la limite de récursion

On peut la connaitre en faisant :

sys.getrecursionlimit()

Et on peut la changer avec

x= 1001
sys.getrecursionlimit(x)

La valeur d'origine est de 1000

Vous êtes arrivé à la fin, bravo! Si vous avez des questions, n'oubliez pas de les poser. A la prochaine !

Vous pourrez retrouver une bonne partie des articles de ce compte sur ce repo.

Pour accéder directement la section que vous regardez actuellement cliquer ici.

Dernier article de la série : Python Tips 3 - Convert two lists into a dictionary