PHP Master | Comprendre la récursivité

Points de base

• Recursion est une méthode de résolution de problèmes qui implique la fonction qui s'appelle directement ou indirectement (via une boucle d'appel de fonction). Il est particulièrement utile lorsqu'il s'agit d'itérer à travers les arbres et les listes ou la plupart des types O (n log n).
• Les fonctions récursives doivent avoir un boîtier de base ou une clause de protection pour les empêcher de se dire infiniment, ce qui entraîne une erreur de débordement de pile. Cet exemple de base est une condition qui empêche la fonction de passer d'autres appels récursifs lorsqu'une condition spécifique est remplie.
• Il existe deux types de récursivité: la récursivité directe et la récursivité indirecte. La récursivité directe signifie que la fonction s'appelle directement, tandis que la récursivité indirecte signifie que la fonction s'appelle indirectement via une autre fonction. Cet article se concentre sur la récursivité directe.
• Bien que la récursivité puisse être un outil puissant, il doit être utilisé avec prudence. PHP n'optimise pas les fonctions récursives, et elles ne sont généralement pas aussi efficaces et rapides que leurs homologues itératives. Cependant, la récursivité peut être plus efficace dans certains cas, comme la recherche ou la traversée de profondeurs incertaines dans un système de fichiers.

Dans un post précédent, j'ai écrit sur les itérateurs et comment les utiliser. Aujourd'hui, je veux voir les frères et sœurs itératifs: la récursivité. Cependant, avant de discuter de la récursivité, jetons un coup d'œil à ce code:

<?php
function factorial($number) {
    if ($number < 0) {
        throw new InvalidArgumentException('Number cannot be less than zero');
    }
    $factorial = 1; 
    while ($number > 0) {
        $factorial *= $number;
        $number--;
    }
    return $factorial;
}

Les usines

sont le résultat d'un nombre multiplié par tous les entiers positifs plus petits que ce nombre. Maintenant, réécrivons cet exemple comme ceci:

<?php
function factorial_recursive($number) {
    if ($number < 0) {
        throw new InvalidArgumentException('Number cannot be less than zero');
    }
    if ($number == 0) {
        return 1;
    }
    return $number * factorial_recursive($number - 1);
}

Lorsque nous appelons ces deux fonctions, nous obtenons le même résultat, mais notez que la deuxième fonction calcule factoriel en s'appelant. C'est ce qu'on appelle la récursivité.

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

Les fonctions récursives se réfèrent aux fonctions qui s'appellent directement ou via des boucles d'appels de fonction. La récursivité peut également se référer à une méthode de résolution de problèmes qui résout d'abord une version plus petite du problème, puis utilise ce résultat pour ajouter d'autres calculs pour former une réponse à la question d'origine. En règle générale, dans le processus de résolution de versions plus petites, cette approche résoudra les versions plus petites du puzzle, etc., jusqu'à ce qu'un "exemple de base" facile à résoudre soit atteint. Pour écrire une fonction récursive, vous devez lui fournir une méthode de retour, sinon il continuera de s'appeler pour toujours (ou jusqu'à ce que la pile d'appels éclate, le script expiré ou la mémoire s'épuise). C'est ce qu'on appelle une clause de protection ou un boîtier de base. La forme la plus simple d'une fonction récursive est la suivante:

<?php
function my_recursive_func(args) {
    if (simplest case) {
        // 停止函数无限运行的基例/保护子句
        return simple value;
    }
    else {
        // 使用更简单的参数再次调用函数
        my_recursive_func(argsSimplified);
    }
}

Type récursif

Lorsqu'une fonction s'appelle directement, elle est appelée recursion directe. L'appel final d'une fonction dans une boucle d'appel de fonction est appelé récursivité indirecte. Veuillez consulter l'exemple suivant de récursivité indirecte:

<?php
function A($num) {
    $num -= 1;
    if($num > 0) {  
        echo "A is Calling B($num)\n";
        $num = B($num);
    }
    return $num;
}

function B($num) {
    $num -= 2;
    if($num > 0) {
        echo "B is Calling A($num)\n";
        $num = A($num);
    }
    return $num;
}

$num = 4;
echo "Calling A($num)\n";
echo 'Result: ' . A($num);

<code>Calling A(4)
A is Calling B(3)
B is Calling A(1)
Result: 0</code>

L'exemple ci-dessus est en fait du code inutile, juste pour vous montrer comment une fonction s'appelle indirectement via une autre fonction. L'appel a (n & gt; 4) ou b (n & gt; 4) provoque une fonction appelée à partir d'un autre appel de fonction. Il est important de savoir que les fonctions peuvent s'appeler indirectement comme ceci, mais dans cet article, nous ne traitons que la récursivité directe.

Un exemple pratique

Pour vous montrer la puissance de la récursivité, nous rédigerons une fonction qui recherche des clés dans un tableau et renvoie les résultats.

<?php
function factorial($number) {
    if ($number < 0) {
        throw new InvalidArgumentException('Number cannot be less than zero');
    }
    $factorial = 1; 
    while ($number > 0) {
        $factorial *= $number;
        $number--;
    }
    return $factorial;
}

<?php
function factorial_recursive($number) {
    if ($number < 0) {
        throw new InvalidArgumentException('Number cannot be less than zero');
    }
    if ($number == 0) {
        return 1;
    }
    return $number * factorial_recursive($number - 1);
}

Tout s'est bien passé, mais notez que nous n'avons itéré que la deuxième couche du tableau, donc la recherche de "Fibonacci" dans la troisième couche a échoué. Si nous devions rechercher des tableaux de profondeur incertaine, cela ne serait pas suffisant. Nous pouvons réécrire la recherche comme une fonction récursive:

<?php
function my_recursive_func(args) {
    if (simplest case) {
        // 停止函数无限运行的基例/保护子句
        return simple value;
    }
    else {
        // 使用更简单的参数再次调用函数
        my_recursive_func(argsSimplified);
    }
}

En utilisant des fonctions récursives, nous pouvons rechercher plusieurs couches de tableaux profonds car nous n'avons pas la profondeur des fonctions codées en dur. Il continue de fonctionner jusqu'à itérer toutes les valeurs du tableau.

Recursion de la tête et récursivité de la queue

Dans tous nos exemples jusqu'à présent, nous avons utilisé la récursivité dite de la tête. Lorsqu'une fonction s'appelle, il attend le résultat de l'appel avant de retourner sa propre valeur. Vous pouvez écrire une fonction qui ne fonctionne pas sur la valeur de retour, mais transmet toutes les valeurs requises comme paramètres. C'est ce qu'on appelle l'appel à queue (ou la récursivité de la queue). Cette méthode est généralement préférée car l'exécution du langage peut parfois optimiser les appels, il n'y a donc pas de danger de dynamiser la pile d'appels, mais PHP ne le fait pas. Ce qui suit est notre exemple factoriel, modifié pour passer un appel de queue. Notez que le résultat de l'appel récursif est retourné, plutôt que de le manipuler davantage.

<?php
function A($num) {
    $num -= 1;
    if($num > 0) {  
        echo "A is Calling B($num)\n";
        $num = B($num);
    }
    return $num;
}

function B($num) {
    $num -= 2;
    if($num > 0) {
        echo "B is Calling A($num)\n";
        $num = A($num);
    }
    return $num;
}

$num = 4;
echo "Calling A($num)\n";
echo 'Result: ' . A($num);

Suggestions générales

Tout code qui peut être écrit en itérative peut être écrit en récursivement. Cependant, ce n'est pas toujours facile à faire (même sage). La récursivité est excellente lorsqu'il s'agit d'itérer à travers les arbres et les listes ou la plupart des types O (n log n). La récursivité est plus appropriée que les méthodes itératives lorsque vous devez diviser les problèmes répétitifs, tels que la recherche dans un système de fichiers, et vous devez également vous rendre dans n'importe quel sous-répertoire pour rechercher. La récursivité fonctionne bien lors de la traversée des profondeurs incertaines. N'oubliez pas que PHP n'optimise pas les fonctions récursives, et même si vous les écrivez pour les appels de queue, les fonctions récursives sont généralement inefficaces et plus lentes que leurs homologues itératives, bien qu'ils fassent parfois le travail mieux, comme dans l'exemple de code ci-dessus. La récursivité est généralement l'alternative préférée à l'itération dans la programmation fonctionnelle, de sorte que la plupart des langages fonctionnels optimisent les fonctions récursives. Si vous utilisez xdebug, assurez-vous de vérifier la configuration de votre système. Par défaut, vous limiterez 100 appels récursifs, et si vous dépassez cette limite, votre script lancera une erreur de nidification maximale a été atteinte ". Si vous devez modifier ce paramètre, vous pouvez mettre à jour la valeur de configuration debug.max_nesting_level. Enfin, il est préférable de lire l'explication du tas de pile et de la récursivité provoquant un débordement de pile pour comprendre ce qui arrive pour appeler la pile pendant la récursivité.

Conclusion

Dans cet article, je vous présente beaucoup à la récursivité et à sa comparaison avec l'itération. Je vous ai également montré comment écrire des fonctions récursives, quand les écrire et pourquoi. J'essaie également de vous avertir de certains pièges que vous pourriez rencontrer lors de l'utilisation de la récursivité. La récursivité est comme ça, même de nombreux programmeurs expérimentés peuvent ne pas l'utiliser depuis des années, et beaucoup d'autres n'en ont même jamais entendu parler, ce qui est dommage car c'est un concept vraiment puissant. J'espère que grâce à ce post, je pourrai vous donner suffisamment de connaissances pour commencer à écrire vos propres fonctions récursives. Mais n'oubliez pas que, tout comme l'utilisation du feu, vous devez toujours utiliser cet outil avec prudence.

Image d'Alexandre Duret-Lutz par Flickr

FAQS sur la compréhension de la récursivité dans PHP (FAQ)

Quel est l'exemple de base de la fonction récursive PHP?

L'exemple de base dans les fonctions récursives PHP est une condition qui empêche la fonction de s'appeler infiniment. C'est un élément clé de toute fonction récursive. Sans cas de base, la fonction récursive s'appellera infiniment, ce qui entraîne une erreur de débordement de pile. En PHP, les exemples de base sont généralement définis à l'aide de l'instruction "IF" au début d'une fonction. La fonction vérifie cette condition avant de procéder à l'appel récursif. Si la condition est remplie, la fonction renvoie une valeur et cesse de s'appeler.

Comment fonctionnent les fonctions récursives en PHP?

La fonction récursive de PHP s'appelle dans son propre corps de fonction jusqu'à ce qu'une condition spécifique appelée le cas de base soit satisfaite. Lorsqu'une fonction récursive est appelée, elle effectue une tâche spécifique, puis s'appelle pour répéter la tâche. Ce processus se poursuit jusqu'à ce que le cas de base soit satisfait et que la fonction cesse de s'appeler. Chaque fois qu'une fonction est appelée, une nouvelle couche est créée sur la pile d'appels, stockant les variables et les adresses de retour des appels de fonction. Une fois le boîtier de base rempli, la fonction commence à retourner et détruise la couche de pile d'appel par calque.

Tous les problèmes de PHP peuvent-ils être résolus à l'aide de la récursivité?

Bien que la récursivité puisse être un outil puissant en PHP, tous les problèmes ne peuvent pas ou doivent être résolus à l'aide de la récursivité. La récursivité est mieux adaptée aux problèmes qui peuvent être décomposés en problèmes plus petits et plus similaires, tels que la traversée des répertoires de fichiers ou les tableaux de tri. Cependant, si elle est mal utilisée, la récursivité peut entraîner une utilisation élevée de la mémoire et des erreurs de débordement de pile. Il est également généralement plus lent que les solutions itératives en raison des frais généraux des appels de fonction. Par conséquent, il est très important de comprendre le problème à portée de main et de choisir la bonne approche.

Comment empêcher le débordement de pile dans les fonctions récursives PHP?

Le débordement de pile dans les fonctions récursifs peut être évité en définissant soigneusement les instances de base que la fonction finira par atteindre. Le boîtier de base est une condition, et lorsque cette condition est remplie, la fonction cesse de passer d'autres appels récursifs. Sans cas de base, la fonction s'appellera infiniment, provoquant un débordement de pile. Il est également important de s'assurer que chaque appel récursif rapproche la fonction du cas de base pour éviter une récursivité infinie.

Qu'est-ce que la récursivité de la queue en PHP?

La récursivité de la queue est un type spécial de récursivité, où l'appel récursif est la dernière opération de la fonction. Cela signifie pas besoin de garder une trace des appels de fonction précédents, permettant au compilateur ou à l'interprète d'optimiser la récursivité et de réduire le risque de débordement de pile. Cependant, PHP lui-même ne prend pas en charge l'optimisation récursive de la queue. Ainsi, même si vous pouvez écrire des fonctions récursives de queue dans PHP, elles ne sont pas optimisées et consomment toujours de l'espace de pile pour chaque appel récursif.

Comment comparer la récursivité avec la boucle en php?

La récursivité et la boucle peuvent être utilisées pour répéter un ensemble d'instructions en PHP. Cependant, ils fonctionnent différemment et présentent des avantages et des inconvénients différents. La récursivité est un outil puissant pour résoudre des problèmes complexes qui peuvent être décomposés en problèmes plus petits et plus similaires. Il est particulièrement utile pour traverser des tâches comme les arbres ou les graphiques. Les boucles, en revanche, sont souvent plus adaptées aux tâches répétitives simples. Ils utilisent moins de mémoire que la récursivité et sont peu susceptibles de provoquer un débordement de pile.

Puis-je utiliser la récursivité pour itérer les tableaux en php?

Oui, la récursivité peut être un moyen très efficace de traverser les tableaux (en particulier les tableaux multidimensionnels) en PHP. Vous pouvez utiliser une fonction récursive pour itérer sur chaque élément dans un tableau, et si l'élément lui-même est un tableau, la fonction peut s'appeler pour itérer sur le tableau. Ce processus se poursuit jusqu'à ce que tous les éléments soient accessibles. Cependant, n'oubliez pas que la récursivité peut être plus lente que les solutions itératives et utilisera plus de mémoire, en particulier dans le cas de grands tableaux.

Qu'est-ce que la récursivité mutuelle en PHP?

La récursivité mutuelle fait référence à deux fonctions ou plus qui sont appelées les unes avec les autres dans une boucle. Dans PHP, cela signifie que la fonction a appelle la fonction B, et la fonction B appelle la fonction A. Cela peut être un outil puissant pour résoudre certains types de problèmes, mais il peut également être plus difficile à comprendre et à déboguer qu'une simple récursivité. Comme pour toute fonction récursive, il est important de définir un cas de base pour empêcher la récursivité infinie.

Comment déboguer les fonctions récursives dans PHP?

Les fonctions récursives de débogage dans PHP peuvent être difficiles car la fonction s'appelle plusieurs fois. Cependant, vous pouvez utiliser plusieurs stratégies. Une façon consiste à utiliser une déclaration d'impression ou un débogueur pour suivre l'appel de fonction et afficher l'état des variables à chaque étape. Une autre façon consiste à dessiner un arbre récursif pour visualiser les appels de fonction. Il est également important de revérifier le boîtier de base et le boîtier de récursivité pour s'assurer qu'ils sont corrects.

Quelles sont les limites de l'utilisation de la récursivité en PHP?

Bien que la récursivité puisse être un outil puissant en PHP, il a certaines limites. L'une des principales limites est que si la récursivité est trop profonde, il y a un risque de débordement de pile. En effet, chaque appel récursif ajoute une nouvelle couche à la pile d'appels et la taille de la pile est limitée. En raison des frais généraux des appels de fonction, la récursivité peut également être plus lente que les solutions itératives et utilisera plus de mémoire. De plus, les fonctions récursives peuvent être plus difficiles à comprendre et à déboguer que les solutions itératives.

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!