Le processus dans lequel une fonction appelle elle-même directement ou indirectement est appelée récursion et la fonction correspondante est appelée une fonction récursive.
En utilisant un algorithme récursif, certains problèmes peuvent être résolus assez facilement. Tours de Hanoi (TOH), traversées d’arbres en ordre / en pré-ordre / post-ordre, DFS du graphe, etc. sont des exemples de ces problèmes.

Par exemple, nous pouvons définir l'opération "trouver le chemin du retour" comme suit:

1. Si vous êtes à la maison, arrêtez de bouger.
2. Faites un pas.
3. "trouve ton chemin à la maison".

Ici, la solution pour trouver votre chemin de retour est de deux étapes (en faite trois étapes). D'abord, nous ne rentrons pas à la maison si nous sommes déjà à la maison. Deuxièmement, nous faisons une action très simple qui rend notre situation plus simple à résoudre. Enfin, refaire l'ensemble de l'algorithme.

Tous les algorithmes récursifs doivent avoir les éléments suivants:

1. Scénario de référence ou de base (c.-à-d. quand arrêter)
2. Travailler vers le cas de base
3. Appel récursif (c'est-à-dire appeler nous-mêmes)

Le "Travailler vers le cas de base" consiste à simplifier le problème (par exemple, diviser la liste en deux parties, chacune plus petite que l'originale).
L'appel récursif est l'endroit où nous utilisons le même algorithme pour résoudre une version plus simple du problème.
Le cas de base est la solution au problème "le plus simple" possible (par exemple, le cas de base du problème 'trouver le plus grand nombre dans une liste' serait si la liste ne comportait qu'un seul numéro ... et par définition s'il y avait un seul nombre, c'est le plus grand).

L'idée est de représenter un problème en termes d'un ou plusieurs petits problèmes, et d'ajouter une ou plusieurs conditions de base qui arrêtent la récursion.
Par exemple, nous calculons la factorielle n si nous connaissons la factorielle de (n-1). Le cas de base pour factorielle serait n = 0. Nous retournons 1 lorsque n = 0.

Si le cas de base n'est pas atteint ou n'est pas défini, le problème de débordement de pile peut survenir. Prenons un exemple pour comprendre cela.

    fonction factorielle(n)
        SI n==50 ALORS
            retourner 1
        SINON
            retourner n*factorielle(n-1)
    
    factoriel(30)

Si factorielle(30) est appelée, elle appellera factorielle(29), factorielle(28), factorielle(27), etc., mais le nombre n'atteindra jamais 50.
Le cas de base n'est donc pas atteint. Si la mémoire est épuisée par ces fonctions sur la pile, cela provoquera une erreur de débordement de pile.

Une fonction fct est de récursive directe si elle appelle la même fonction fct.
Une fonction fct est de récursive indirecte si elle appelle une autre fonction, par exemple fct_new et fct_new appelle fct directement ou indirectement.

    fonction fct()
        fct_new()
    
    fonction fct_nex()
        fct()

Lorsqu'une fonction est appelée, la mémoire lui est allouée sur la pile.
Une fonction récursive s’appelle elle-même, la mémoire d’une fonction appelée est allouée en plus de la mémoire allouée à la fonction appelante et une copie différente des variables locales est créée pour chaque appel de fonction.
Lorsque le cas de base est atteint, la fonction renvoie sa valeur à la fonction par laquelle elle est appelée, la mémoire est désallouée et le processus continue.

Prenons un exemple simple pour bien comprendre le fonctionnement de la récursivité.

            fonction factorielle(n)
                SI n=1 ALORS
                    retourner 1
                SINON
                    Ecrire(fact)
                    fact=n*factorielle(n-1)
                    retourner fact
            

                def factorielle(n):
                    if n == 1:
                        return 1
                    else:
                        print(n)
                        fact = n * factorielle(n-1)
                        print(fact)
                        return fact
                
                factorielle(3)
            

lorsque factorielle(3) est appelée, la mémoire est allouée à factorielle(3), la variable locale n est initialisée à 3 et les instruction de 1 à 4 est placées dans la pile.
comme indiqué dans le diagramme ci-dessous, donc premièrement la fonction affiche 3 et appelle factorielle(2), factorielle (2) affiche 2 et appelle factorielle(1). factorielle(1) retourne 1 à factorielle(2), les instruction restantes de factorielle(2) est exécutées (calculer fact=2*1, afficher 2) puis retourne 2 à factorielle(3), les instruction restantes de factorielle(3) est exécutées (calculer fact=3*2; afficher 6 et retourner la valeur finale 6 à l'utilisateur)
à la fin la pile est désallouée

Notez que les programmes récursifs et itératifs ont les mêmes capacités de résolution de problèmes, c’est-à-dire que tous les programmes récursifs peuvent être écrits de manière itérative et vice versa.
Le programme récursif a besoin plus d'espace qu'un programme itératif, car toutes les fonctions resteront dans la pile jusqu'à ce que le cas de base soit atteint. En outre, le temps requis est plus long en raison d'appels de fonction.

La récursivité fournit un moyen simple et propre d’écrire du code. Certains problèmes sont intrinsèquement récursifs, tels que les parcours d'arbres, la tour de Hanoi, etc. Pour de tels problèmes, il est préférable d'écrire du code récursif. Nous pouvons également écrire ces codes de manière itérative à l'aide de pile.