Les joies de la Récursivité

rem ============================================================================
rem          Utilisation de la récursivité
rem       Routines tortue (turtle) comme en Logo
rem                   Par Papydall
rem ============================================================================
' ATTENTION : Ce code est destiné au compilateur et non à l'interpréteur Panoramic
rem ============================================================================

Caption 0, "!!! VIVE LA RECURSIVITE !!!"
Init_Turtle()

 Nouveau() : carre1(200) : wait 1000
 Nouveau() : carre2(300) : wait 1000
 Nouveau() : carre3(50)  : wait 1000
 Nouveau() : carre3(150) : wait 1000
 Nouveau() : carre4(50)  : wait 1000
 Nouveau() : carre4(150) : wait 1000
 Nouveau() : Courbe_C(10,10): wait 1000
 Nouveau() : Carre_Fractal(300,8) : wait 1000
 Nouveau() : Curly_Fractal(25) : wait 1000
 Nouveau() : hilbert(5,90,10) : wait 1000
 Nouveau() : Peano(6,90,12)   : wait 1000
 Nouveau() : Rosace(200,10)   : wait 1000
 Nouveau() : Laby(5)   : wait 1000
 Nouveau() : Cercle(5) : wait 1000
 Nouveau() : Spaghetti(30): wait 1000
 Nouveau() : Squaggle(20) : wait 1000
 Nouveau() : y = yc + 200 : Arbre(350) : wait 1000
end
rem ============================================================================
' Initialisation de la tortue graphique
' La tortue se trouve au centre de la fénêtre et est dirigée vers le Nord
SUB Init_Turtle()
    dim xc,yc,x,y,cap,angle, pi,rad
    width 0,screen_x - 200 : height 0,screen_y - 200 : top 0,100 : left 0,100
    color 0,0,0,0 : 2d_pen_color 255,255,0
    xc = width(0)/2 : yc = height(0)/2 : pi = acos(-1) : cap = pi/2
    x = xc : y = yc : angle = cap : rad = pi/180
    2d_poly_from x,y
END_SUB
rem ============================================================================
' Pour débuter un nouveau dessin
' Effacer l'écran et remettre la tortue à sa place
' (au centre de la fenêtre et dirigée vers le nord)
SUB Nouveau()
    cls
    x = xc : y = yc : angle = cap : 2d_poly_from x,y
END_SUB
rem ============================================================================
' Avancer de pas pixels en traçant un trait avec la couleur en cours
' Si le pas est négatif, ça correspond à Réculer de pas pixels
SUB Forward(pas)
    dim_local x1,y1,x2,y2,a
    x1 = x : y1 = y : a = angle
    x2 =  x + pas * cos(a) : y2 = y - pas * sin(a)
    2d_poly_to x2,y2 : x = x2 : y = y2
END_SUB
rem ============================================================================
' Tourner à gauche (sens trigonométrique) de a degrés
SUB Turn_Left(a)
    angle = angle + a * rad
END_SUB
rem ============================================================================
' Tourner à droite (sens horraire) de a degrés
SUB Turn_Right(a)
    angle = angle - a * rad
END_SUB
rem ============================================================================
' Procédure de tracé d'un carré
SUB Carre1(cote)
    dim_local i
    for i = 1 to 4 : forward(cote) : turn_right(90) : next i
END_SUB
rem ============================================================================
' Procédure récursive de tracé des carrés imbriqués
SUB Carre2(cote)
    dim_local i
    if cote > 100
       for i = 1 to 4 : forward(cote) : turn_right(90) : next i : wait 10
       Carre2(cote-10)
    end_if
END_SUB
rem ============================================================================
' Procédure récursive de tracé des carrés imbriqués
SUB Carre3(cote)
    dim_local i
    for i = 1 to 4  : forward(cote) : turn_right(90) : next i
    if cote < 100
       carre3(cote+10)
    else
       forward(cote) : turn_right(30)
       for i = 1 to 3 : forward(cote) : turn_right(120) : next i
    end_if

END_SUB
rem ============================================================================
' Procédure récursive de tracé des carrés imbriqués
SUB Carre4(cote)
    dim_local i
    for i = 1 to 4  : forward(cote) : turn_right(90) : next i
    if cote < 100
       carre4(cote+10)
    else
       forward(cote) : turn_right(30)
    end_if
    for i = 1 to 3 : forward(cote) : turn_right(120) : next i
END_SUB
rem ============================================================================
' Procédure récursive de tracé de la courbe de C
SUB Courbe_C(taille,niveau)
    if niveau = 0
       forward(taille)
    else
       Courbe_C(taille,niveau-1)
       turn_right(90)
       Courbe_C(taille,niveau-1)
       turn_left(90)
    end_if
      
END_SUB
rem ============================================================================
' Procédure récursive de tracé des carrés
SUB Carre_Fractal(cote,niveau)
    dim_local i
    if niveau > 0
       for i = 1 to 4
          forward(cote) : turn_right(90)
          Carre_Fractal(cote * 0.4, niveau-1)
       next i
    end_if
END_SUB
rem ============================================================================
' Procédure récursive de tracé des carrés imbriqués
SUB Curly_Fractal(taille)
    dim_local i
    if taille > = 0.5
       for i = 1 to 360
           select i
              case 5  : turn_left(90) : Curly_Fractal(taille/2) : turn_right(90)
              case 10 : turn_left(90) : Curly_Fractal(taille/5) : turn_right(90)
              case 15 : turn_left(90) : Curly_Fractal(taille/5) : turn_right(90)
              case 20 : turn_left(90) : Curly_Fractal(taille/4) : turn_right(90)
              case 25 : turn_left(90) : Curly_Fractal(taille/5) : turn_right(90)
              case 30 : turn_left(90) : Curly_Fractal(taille/8) : turn_right(90)
           end_select
           forward(taille) : turn_right(i)
       next i
       turn_right(180)
    end_if
END_SUB
rem ============================================================================
' Procédure récursive de tracé de la courbe de Hilbert
SUB Hilbert(n,a,h)
    if n > 0
       turn_right(a)
       hilbert(n-1,0-a,h) : forward(h)   : turn_left(a)
       hilbert(n-1,a,h)   : forward(h)
       hilbert(n-1,a,h)   : turn_left(a) : forward(h)
       hilbert(n-1,0-a,h) : turn_right(a)
    end_if
end_sub
rem ============================================================================
' Procédure récursive de tracé de la courbe de Peano
SUB Peano(n,a,h)
    if n > 0
       turn_right(a)
       Peano(n-1,0-a,h) : forward(h)
       peano(n-1,a,h)   : forward(h)
       Peano(n-1,0-a,h) : turn_left(a)
    end_if
END_SUB
rem ============================================================================
' Procédure  de tracé d'une rosace
SUB Rosace(c,n)
    dim_local i,j
    for i = 1 to n
        for j = 1 to 4 : forward(c) : turn_right(90+10) : next j
    next i
end_sub
rem ============================================================================
' Procédure récursive de tracé d'un labyrinthe
SUB Laby(n)
    if n < 400
       forward(n) : turn_right(90) : Laby(n+5)
    end_if
END_SUB
rem ===========================================================================
' Procédure  de tracé d' un cercle
SUB Cercle(n)
    dim_local i
    for i = 1 to 36 : forward(n) : turn_right(10) : next i
END_SUB
rem ===========================================================================
' Procédure récursive de tracé des cercles imbriqués
SUB Spaghetti(n)
    Cercle(n)
    if n > 0 then turn_right(45) : Spaghetti(n-1)
END_SUB
rem ===========================================================================
' Procédure
SUB Squaggle(n)
    dim_local i
    for i = 1 to n
        forward(50) : turn_right(150)
        forward(60) : turn_right(100)
        forward(30) : turn_right(90)
    next i
END_SUB
rem ============================================================================
' Procédure récursive de tracé d'un bel arbre
SUB Arbre(taille)
    if taille < 5
       forward(taille) : forward(0-taille)
    else
       forward(taille/3) : turn_left(30) : Arbre(taille*2/3) : turn_right(30)
       forward(taille/6) : turn_right(25) : Arbre(taille/2) : turn_left(25)
       forward(taille/3) : turn_right(25) : Arbre(taille/2) : turn_left(25)
       forward(taille/6) : forward(0-taille)
    end_if
END_SUB
rem ============================================================================

rem ============================================================================
rem                          QuickSort
rem            Algorithme récursif de tri rapide
rem ============================================================================
' Exemple de tri sur un tableau de 10000 cases contenant chacune un nombre
' aléatoire de 0 à 9999
' Le tri est extrêmement rapide, même pour des grands tableaux
' Pour apprécier cette rapidité, activez la ligne 12 en supprimant l'apostrophe du REM
rem ============================================================================
Init()            : ' Initialisation du tableau de 10000 éléments
QuickSort(0,9999) : ' Tri du tableau
' message "OK"
Affiche_Tab()     : ' Affichage du tableau sous forme de 10 listes de 1000 valeurs
end
rem ============================================================================
SUB Init()
    dim tab(9999) : ' tableau de dix mille éléments
    dim_local i
    full_space 0
' Créer 10 listes pour contenir 1000 valeurs chacune
    for i = 1 to 10
        list i : top i,20 : left i,50+(i-1) * 150 : height i,screen_y - 200
    next i
' Initialiser le tableau avec des valeurs aléatoires comprises entre o et 9999
    for i = 0 to 9999 : tab(i) = int(rnd(10000)) : next i
END_SUB
rem ============================================================================
' Afficher le contenu des 10 listes de 1000 nombres chacune
SUB Affiche_Tab()
    dim_local i
    for i = 0 to 9999 : item_add 1 + int(i/1000),str$(i) + " : " + str$(tab(i)) : next i
END_SUB
rem ============================================================================
' Trier le tableau en utilisant l'algorithme récursif QuickSort (tri rapide)
SUB QuickSort(debut, fin)
    dim_local pivot, gauche, droite, temp
    pivot = debut : gauche = debut : droite = fin
    repeat
       if tab(gauche) >= tab(droite)
' échanger tab(droite) et tab(gauche
       temp = tab(gauche) : tab(gauche) = tab(droite) : tab(droite) = temp
       pivot = gauche + droite - pivot : ' nouvelle position du pivot
' pivot est alors égal à droite ou à gauche car pivot était égal
' avant à gauche ou à droite. c'est un raccourci élégant pour
' "if pivot = gauche then pivot = droite : else : pivot = gauche"
       end_if
       if pivot = gauche then droite = droite - 1 : else : gauche = gauche + 1
    until gauche = droite
    if debut < gauche - 1 then QuickSort(debut, gauche - 1) : ' appel récursif sur la partie gauche
    if fin   > droite + 1 then QuickSort(droite + 1, fin)   : ' appel récursif sur la partie droite
END_SUB
rem ============================================================================