Récursivité

[snsdtiti]

Bonjour !

J'avais un exercice à faire sur la récursivité à coder en java, le problème c'est que même avec la correction je ne comprend absolument rien TT
Il y aurait-il une âme charitable pour me sortir de la ?
PS : bob c'est une tortue qui bouge ^^'

public void vonKoch(double l, int n){
    	//vonKoch(l,n), n>=1
    	//prerequis n>=0

        bob.speed(100);
    	if(n==0){
    		bob.forward(l); 

    	}
    	else{
            
    		vonKoch(l/3, n-1); 
    		bob.left(60); 
    		vonKoch(l/3, n-1); 
    		bob.right(120); 
    		vonKoch(l/3, n-1); 
    		bob.left(60); 
    		vonKoch(l/3, n-1);
    		
    	}

    }

-----

[pm42]

Qu'est ce que tu ne comprends pas ? Tu as déjà regardé les définitions les plus simples de la récursivité comme la factorielle ?

Tu connais les définitions par récurrence en maths où on définit quelque chose à partir de la "version précédente" ? Ici, c'est la même chose.
On dit que la courbe de niveau 0, c'est juste un segment.
La courbe de niveau 1, c'est 1 segment avec un triangle équilatéral au milieu dont la base fait 1/3. Donc là on a donc remplacé le segment par 4 segments.
Pour le niveau 2, on fait la même chose sur les 4 segments du niveau 1

[snsdtiti]

Merci pour ta réponse, j'ai compris comment fonctionne la récursivité pour les factorielles ^^

Mais je comprend que l c'est la longueur mais n je ne vois pas trop ce que c'est, ça ma l'air d'être une sorte de compteur ?

On dit que la courbe de niveau 0, c'est juste un segment.

jusque la ça va mais
pourquoi est ce que le niveau 1 c'est

1 segment avec un triangle équilatéral au milieu dont la base fait 1/3

? Je comprend qu'on coupe l en 3 morceaux (l/3) mais pourquoi un triangle ? si on pars de la version précédente c'est un segment de longueur l non ?

[Deedee81]

Salut,

mais n je ne vois pas trop ce que c'est, ça ma l'air d'être une sorte de compteur ?

C'est ça. On appelle avec 10 par exemple, et il va s'appeler (plusieurs fois) avec 9, puis 8.... jusque 0. A chaque fois il divise la distance par 3.

Pour bien visualiser ce que ça fait, écrire à la main pour n petit, disons 3 ou 2, et voir les appels successifs que seront fait à left, right, etc...
Et le dessiner.
(faut partir de n pas trop grand car le nombre d'appels grimpes vite puisque la fonction s'appelle elle-même quatre fois !!!!)

Ca devrait dessiner un début de fractale de Von Koch

[A voir en vidéo sur Futura]

[snsdtiti]

Merci ^^

si n=3 par exemple :
On entre dans la boucle else, mais à partir de la on a VonKoch(l/3, n-1); bob.left(60); vonKoch(l/3, n-1);
mais qu'est ce que ça veut dire exactement un trait de longueur l/3 et tourne à gauche à 60° puis un trait l/3 ? c'est bien dans ce sens la ?

Ah je vois le truc mais pourquoi n==0 ça fait bob.forward ? on devrait s'arrêter à la fin du else non ?

[umfred]

suis ce que fait le programme: n=1
on lance vonkoch(l/3,0) (n-1=0) =>n=0, bob avance de l/3; on revient
bob tourne à gauche de 60° (je suppose que c'est ce que fait bob.left(60)
on lance vonKoch(l/3,0) => n=0, bob avance de l/3; on revient
bob tourne à droite de 120°
on lance vonKoch(l/3,0) => n=0, bob avance de l/3; on revient
bob tourne à gauche de 60°
on lance vonKoch(l/3,0) => n=0, bob avance de l/3; on revient
on a fini
on obtient une forme qui ressemble à _/\_ (chaque segment faisant l/3)

[champetre]

Bonjour,

Ça me fatigue de voir le calcul d'une factorielle systématiquement cité pour expliquer la récursivité !

En effet, la définition montre que le calcul est explicitement à faire avec une vulgaire boucle POUR.

J'en vois déjà qui vont venir dire "c'est juste pour apprendre" mais justement : on n'apprend pas à conduire en étudiant la mécanique !

[pm42]

Ça me fatigue de voir le calcul d'une factorielle systématiquement cité pour expliquer la récursivité !

C'est moins fatiguant que les gens qui interviennent uniquement pour critiquer sans être capable de faire la moindre contribution constructive.

Et pour la factorielle, on l'utilise pour l'enseignement justement parce que cela permet de montrer comme sa définition récursive mathématique se traduit telle quelle en programmation.
Et ce d'autant plus que certains langages ou méthodes de programmation n'ont pas de boucle for (ou POUR si ça te fait plaisir), en tout cas pas telle que tu l'entends.

[Deedee81]

EDIT Croisement avec pm42 toujours aussi piquant

Ça me fatigue de voir le calcul d'une factorielle systématiquement cité pour expliquer la récursivité !

C'est parce que c'est une des plus simple
(on peut montrer que toute procédure récursive peut être transformée en procédure itérative)


Faut bien commencer à marcher avant d'apprendre à courir

Perso j'ai jamais râlé du fait de voir le nombre de bouquins d'apprentissage à la programmation commençant par 'print coucou"

[pm42]

EDIT Croisement avec pm42 toujours aussi piquant

Pas du tout, ça, c'est la version light, tout en litote parce que la modération est sans pitié

[Deedee81]

Pas du tout, ça, c'est la version light, tout en litote parce que la modération est sans pitié

Moi, sans pitié ? On m'appelle le nounours vert

[snsdtiti]

Merci à tous pour vos réponses haha, j'ai un peu mieux compris comment ça fonctionnait ^^

Je soucis c'est que quand n=3 c'est sensé faire _/\_ mais quand je lance le programme ça me fait une "multitude" de VanKoch ^^'
pour l = 500 et n = 3
et la j'avoue que je comprend pas trop hehe

[pm42]

Je soucis c'est que quand n=3 c'est sensé faire _/\_

Non, ça, c'est n=1.
n=0 on fait juste un segment ___
n=1 _/\_
n=2 : on ne peut pas le dessiner facilement avec des caractères

[umfred]

Merci à tous pour vos réponses haha, j'ai un peu mieux compris comment ça fonctionnait ^^

Je soucis c'est que quand n=3 c'est sensé faire _/\_ mais quand je lance le programme ça me fait une "multitude" de VanKoch ^^'
pour l = 500 et n = 3
et la j'avoue que je comprend pas trop hehe

bah j'ai montré que pour n=1 on avait la forme _/\_ dans mon message #6 (enfin il me semble ...)

[snsdtiti]

Oui pardon UmFred c'est moi qui ai mal relu ^^'

Je suis vraiment désolée j'ai un peu de mal... mmh n tous au long de la fonction ne change pas si ?
si n=2 par exemple, à la fin de la boucle else, il sera toujours égal à 2 et du coup c'est pas sensé faire un truc à l'infini ?

[pm42]

n tous au long de la fonction ne change pas si ?
si n=2 par exemple, à la fin de la boucle else, il sera toujours égal à 2 et du coup c'est pas sensé faire un truc à l'infini ?

Quand tu appelles l'étape suivant, tu passes n-1. Donc si VonKoch recoit n=2, il fait ses trucs puis s'appelle avec n=1 qui lui même avec appeler avec n=0.

C'est vraiment pareil que la factorielle déjà citée.

[snsdtiti]

Ohh merci à tous !! Vraiment !! j'ai compris !!! TT

Je m'étais complètement emmêlé les pinceaux hehe oh la la c'est tout bête mais faut vraiment le voir ^^'
Franchement merci !!

[Deedee81]

Salut,

oh la la c'est tout bête mais faut vraiment le voir ^^'

Un des nombreux petit déclics qu'on a tous vécus et qui feront de toi un grand programmeur