Maison >Java >javaDidacticiel >Quelle est la différence entre la récursivité et l'itération en Java ?

Quelle est la différence entre la récursivité et l'itération en Java ?

王林
王林avant
2023-05-02 19:25:051126parcourir

1. La différence entre récursivité et itération

  • Lorsqu'une entité s'appelle, le programme est appelé récursif. 调用自身时,程序称为递归

  • 当存在循环(或重复)时,程序称为迭代调用

  • 示例:求一个数的阶乘的程序

 时间复杂度比较

  • 查找递归的时间复杂度比迭代更难。

  • 递归:递归的时间复杂度可以通过根据先前的调用找到第 n 次递归调用的值来找到。因此,根据基本情况找到目标情况,并根据基本情况求解,可以让我们了解递归方程的时间复杂度。

  • 迭代:迭代的时间复杂度可以通过找到循环内重复的循环数来找到。

 用法比较

  •  使用这些技术中的任何一种都是时间复杂度和代码大小之间的权衡。

  • 如果时间复杂度是重点,递归调用的次数会很大,那么最好使用迭代。

  • 但是,如果时间复杂度不是问题而代码的短小是问题,那么递归将是可行的方法。

  • 递归:递归涉及再次调用相同的函数,因此代码长度非常短。然而,正如我们在分析中看到的那样,当递归调用数量相当多时,递归的时间复杂度可能会呈指数级增长。因此,递归的使用在更短的代码中是有利的,但时间复杂度更高。

  • 迭代:迭代是代码块的重复。这涉及较大的代码量,但时间复杂度通常低于递归。

 开销

  • 与迭代相比,递归有大量的开销。

  • 递归:递归有函数重复调用的开销,即由于重复调用同一个函数代码的时间复杂度增加了很多倍

  • 迭代:迭代不涉及任何此类开销。

 无限重复

  •  递归中的 Infinite Repetition 会导致 CPU crash,但在迭代中,当内存耗尽时它会停止。

  • 递归:在Recursion中,由于指定的基本条件错误,可能会出现无限递归调用,在永远不会为假的情况下,不断调用函数,这可能会导致系统CPU崩溃。

  • 迭代

Lorsqu'il y a une boucle (ou répétition), le programme est appelé un appel itératif. Comparaison de la complexité temporelleTrouver la complexité temporelle de la récursivité est plus difficile que l'itération. Récursion : La complexité temporelle de la récursion peut être trouvée en trouvant la valeur du nième appel récursif en fonction des appels précédents. Par conséquent, trouver le cas cible sur la base du cas de base et le résoudre sur la base du cas de base nous permet de comprendre la complexité temporelle de l’équation récursive. Itération : La complexité temporelle de l'itération peut être trouvée en trouvant le nombre de boucles répétées dans la boucle. Comparaison d'utilisation L'utilisation de l'une de ces techniques est un compromis entre la complexité temporelle et la taille du code. Si la complexité temporelle est au centre de l'attention et que le nombre d'appels récursifs sera important, alors il est préférable d'utiliser l'itération. Cependant, si la complexité temporelle n'est pas un problème et que la brièveté du code l'est, alors la récursivité serait la voie à suivre. Récursion : La récursion implique d'appeler à nouveau la même fonction, la longueur du code est donc très courte. Cependant, comme nous l’avons vu dans notre analyse, la complexité temporelle de la récursivité peut croître de façon exponentielle lorsque le nombre d’appels récursifs est considérable. Par conséquent, l’utilisation de la récursivité est avantageuse dans un code plus court, mais avec une complexité temporelle plus élevée. Itération : L'itération est la répétition d'un bloc de code. Cela implique une plus grande quantité de code, mais la complexité temporelle est généralement inférieure à celle de la récursivité. Overhead Par rapport à l'itération, la récursivité a beaucoup de surcharge. Récursion : La récursion a la surcharge des appels de fonction répétés, c'est-à-dire, en raison des appels répétés à la même fonction, de la complexité temporelle du code augmente plusieurs fois code>. Itération : l'itération n'implique pas une telle surcharge. Répétition infinie La répétition infinie en récursion provoquera un crash du processeur, mais dans l'itération, elle s'arrêtera lorsque la mémoire sera épuisée. Récursion : En récursion, des appels récursifs infinis peuvent se produire en raison d'erreurs dans les conditions de base spécifiées. Les fonctions sont appelées en continu alors qu'elles ne sont jamais fausses, ce qui peut provoquer des pannes du processeur. Itération : une itération infinie due à une affectation d'itérateur ou à une erreur d'incrémentation ou à une mauvaise condition de terminaison entraînera une boucle infinie, qui peut ou non entraîner une erreur système, mais s'arrêtera définitivement la poursuite de l'exécution du programme. La fonction récursiveitérativedefine s'appelle elle-même. Un ensemble d'instructions exécutées à plusieurs reprises. Applicationspour la fonctionnalité. Pour les boucles. Termination
Exemple : Programme pour trouver la factorielle d'un nombre

Dans le cas de base, il n'y aura aucun appel de fonction ici.

🎜Lorsque la condition de terminaison de l’itérateur n’est plus remplie. 🎜🎜🎜🎜Utilisation🎜🎜À utiliser lorsque la taille du code doit être petite et que la complexité temporelle n'est pas un problème. 🎜🎜À utiliser lorsque la complexité temporelle doit être équilibrée par rapport à la taille du code étendue 🎜🎜🎜🎜Taille du code 🎜🎜Moins de code 🎜🎜Plus de code 🎜🎜🎜🎜Complexité temporelle 🎜🎜complexité temporelle très élevée (généralement exponentielle). 🎜🎜La complexité temporelle est relativement faible (généralement logarithme polynomial). 🎜🎜🎜🎜Complexité spatiale🎜🎜La complexité spatiale est supérieure à l'itération. 🎜🎜La complexité spatiale est faible. 🎜🎜🎜🎜Heap🎜🎜La pile ici est utilisée pour stocker les variables locales lorsque les fonctions sont appelées. 🎜🎜N'utilise pas de pile. 🎜🎜🎜🎜Vitesse🎜🎜L'exécution est lente car elle entraîne la maintenance et la mise à jour de la pile. 🎜🎜Généralement, c'est plus rapide que la récursivité car il n'utilise pas la pile. 🎜🎜🎜🎜Storage🎜🎜La récursion utilise plus de mémoire que l'itération. 🎜🎜Pas de surcharge puisqu'il n'y a pas d'appels de fonction dans l'itération. 🎜🎜🎜🎜Elevated🎜🎜a la surcharge des appels de fonction répétés. 🎜🎜Pas de surcharge puisqu'il n'y a pas d'appels de fonction dans l'itération. 🎜🎜🎜🎜Répétition infinie🎜🎜Si une fonction récursive ne satisfait pas à la condition de terminaison ou est indéfinie ou si le cas de base n'est jamais atteint, cela provoquera une erreur de débordement de pile et le système peut planter en récursion infinie. 🎜🎜Si la condition de contrôle de l'instruction d'itération n'est jamais fausse ou si la variable de contrôle n'atteint pas la valeur terminale, cela provoquera une boucle infinie. Dans une boucle infinie, il utilise encore et encore les cycles du processeur. 🎜🎜🎜🎜🎜2.

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!

Déclaration:
Cet article est reproduit dans:. en cas de violation, veuillez contacter admin@php.cn Supprimer