Récursivité basée sur la structure de données PHP

Cet article présente principalement la récursion sur la base de la structure des données PHP. Il a une certaine valeur de référence. Maintenant, je le partage avec vous. Les amis dans le besoin peuvent s'y référer

Qu'est-ce que la récursivité ?

Comme mentionné précédemment, la récursivité est une solution qui décompose les gros problèmes en petits. De manière générale, la récursion est appelée un appel à la fonction elle-même. Cela peut paraître étrange de dire cela, mais en fait, en récursivité, la fonction doit s'appeler elle-même.

Une châtaigne

Par exemple, en mathématiques, nous connaissons tous la notion de « factorielle ». Par exemple, la factorielle de 5 est 5*4*3*2*1.

• 5 ! = 5*4 !

• 4 ! = 4*3 !

• 3 ! = 3*2 !

• 2 ! = 2*1 !

• 1 ! = 1 * 0 !

• 0 ! = 1

Nous pouvons résumer la règle pour trouver la factorielle de n, c'est-à-dire n = n * (n -1) !

Cela reflète la récursion. Vous pouvez en déduire que nous avons transformé étape par étape la factorielle de 5 en un autre petit problème.

Caractéristiques des algorithmes récursifs

• Chaque appel récursif doit être basé sur un petit sous-problème. Par exemple, la factorielle de 5 est la factorielle de 5 fois 4.

• La récursivité doit avoir un cas de base. Par exemple, le cas de base de factoriel est 0. Lorsque la condition est 0, la récursion s'arrête.

• Évitez les appels en boucle pendant la récursion, sinon l'ordinateur affichera une erreur de débordement de pile à la fin.

function factorial(int $n): int
{
    if ($n = 0) {
        return 1;
    }
    
    return $n * factorial($n - 1);
}

En regardant le code ci-dessus, nous pouvons voir que nous avons une condition de base pour la solution du problème factoriel, qui est que lorsque n est 0, nous renvoyons 1. Si cette condition n'est pas remplie, nous renvoyons n fois factorial(n) , ce qui est conforme aux première et troisième propriétés récursives. Nous évitons les appels en boucle car nous divisons chaque appel récursif en un sous-problème plus petit du problème plus vaste. L'idée d'algorithme ci-dessus peut être exprimée comme suit :

Récursion Vs Itération

Nous pouvons également utiliser la méthode itérative pour implémenter le code récursif ci-dessus

function factorial(int $n): int
{
    $result = 1;
    
    for ($i = $n; $i > 0; $i--) {
        $result*= $n;
    }
    
    return $result;
}

Si un problème Il peut être facilement résolu par itération, pourquoi utilisons-nous la récursivité ?

La récursion est utilisée pour traiter des problèmes plus complexes. Tous les problèmes ne peuvent pas être résolus simplement par itération. La récursion utilise des appels de fonction pour gérer la pile d'appels, donc la récursion utilise plus de temps et de mémoire que l'itération. De plus, en itération, nous aurons un résultat à chaque étape, mais en récursion, nous devons attendre la fin de l'exécution du cas de base avant d'avoir un résultat. En regardant l'exemple ci-dessus, nous constatons que dans l'algorithme récursif, nous n'avons aucune variable ou déclaration pour enregistrer les résultats, tandis que dans l'algorithme itératif, nous utilisons $result pour enregistrer les résultats renvoyés à chaque fois.

Séquence de Fibonacci

En mathématiques, la séquence de Fibonacci est une séquence spéciale d'entiers. Chaque nombre de la séquence est généré par la somme de deux autres nombres. Les règles sont les suivantes :

function fibonacci($n)
{
    if ($n == 0) {
        return 0;
    }
    
    if ($n == 1) {
        return 1;
    }
    
    return fibonacci($n - 1) + fibonacci($ - 2);
}

Plus grand facteur commun

Un autre problème courant utilisant les algorithmes récursifs est de trouver le plus grand facteur commun de deux nombres.

function gcd(int $a, int $b)
{
    if ($b == 0) {
        return $a;
    }
    
    return gcd($b, $a % $b);
}

Type de récursion

• Récursivité linéaire

dans chaque récursivité Pendant l'appel, la fonction ne s'appelle qu'une seule fois, ce qu'on appelle la récursion linéaire.

• Récursion binaire

En récursion binaire, chaque appel récursif à la fonction s'appelle deux fois. L'algorithme pour résoudre la séquence de Fibonacci est la récursion binaire. De plus, la recherche binaire, l'algorithme diviser pour régner, le tri par fusion, etc. utilisent également la récursion binaire.

• Récursion de queue

Lorsqu'un retour récursif n'a pas d'opérations d'attente, on parle de récursion de queue. Dans l'algorithme de Fibonacci, la valeur de retour doit être multipliée par la valeur de retour de la récursion précédente, elle n'est donc pas récursive en queue, et l'algorithme pour résoudre le plus grand facteur commun est récursif en queue. La récursion de queue est une forme de récursion linéaire.

• Récursion mutuelle

Par exemple, dans chaque appel récursif, A() appelle B(), B() appelle A(), Une telle récursivité est appelée récursivité mutuelle.

• Récursion imbriquée

Lorsqu'une fonction récursive s'appelle récursivement en tant que paramètre, elle est appelée récursion imbriquée. Un exemple courant est la fonction Ackerman, voir l'expression ci-dessous.

En regardant la dernière ligne, vous pouvez voir que le deuxième paramètre est la fonction récursive elle-même.

Section suivante

Le prochain article utilisera la récursivité pour résoudre certains problèmes rencontrés dans le développement réel, tels que la création de classifications de niveau N, la création de commentaires imbriqués, la traversée de fichiers de répertoire, etc.

Ce qui précède représente l'intégralité du contenu de cet article. J'espère qu'il sera utile à l'étude de chacun. Pour plus de contenu connexe, veuillez faire attention au site Web PHP chinois !

Recommandations associées :

Comment obtenir la véritable adresse IP du client en PHP

Comment utiliser Elasticsearch dans PHP

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!