Python Tips - Playing with recursion

by me

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.

Formule de Fibonacci

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:

Recursion tree

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