Une définition par récurrence classique correspond à la programmation récursive : \[ \begin{cases} s(0) = 0 \\ \forall n\in\mathbb{N}-{0} \ \ \ s(n) = n + s(n-1) \end{cases} \]

def somme(n) :
	if n == 0 : return 0
	else : return n + somme(n-1)
	
	
print(somme(5))

Le principe est le suivant :

1. Appel : somme(5).
2. somme(5) doit retourner 5 + somme(4). Mais somme(4) n'est pas connu à ce stade.
3. somme est donc exécutée avec l'argument 4 pour évaluer somme(4). somme(4) doit retourner 4 + somme(3). Mais somme(3) n'est pas connu à ce stade.
4. somme est donc exécutée avec l'argument 3 pour évaluer somme(3). somme(3) doit retourner 3 + somme(2). Mais somme(2) n'est pas connu à ce stade.
5. somme est donc exécutée avec l'argument 2 pour évaluer somme(2). somme(2) doit retourner 2 + somme(1). Mais somme(1) n'est pas connu à ce stade.
6. somme est donc exécutée avec l'argument 1 pour évaluer somme(1). somme(1) doit retourner 1 + somme(0). Mais somme(0) n'est pas connu à ce stade.
7. somme est donc exécutée avec l'argument 0 pour évaluer somme(0). somme(0) retourne la valeur 0.
8. somme(0) étant maintenant connue, on peut terminer l'évaluation de somme(1) : somme(1) = 1 + somme(0) = 1 + 0 = 1.
9. somme(1) étant maintenant connue, on peut terminer l'évaluation de somme(2) : somme(2) = 2 + somme(1) = 2 + 1 = 3.
10. somme(2) étant maintenant connue, on peut terminer l'évaluation de somme(3) : somme(3) = 3 + somme(2) = 3 + 3 = 6.
11. somme(3) étant maintenant connue, on peut terminer l'évaluation de somme(4) : somme(4) = 4 + somme(3) = 4 + 6 = 10.
12. somme(4) étant maintenant connue, on peut terminer l'évaluation de somme(5) : somme(5) = 5 + somme(4) = 5 + 10 = 15.

En bref :

${\displaystyle \begin{array}{ccc}\text{somme}(5)& =& 5+\text{somme}(4)\\ & =& 5+(4+\text{somme}(3))\\ & =& 5+(4+(3+\text{somme}(2)))\\ & =& 5+(4+(3+(2+\text{somme}(1))))\\ & =& 5+(4+(3+(2+(1+\text{somme}(0)))))\\ & =& 5+(4+(3+(2+(1+0))))\\ & =& 5+(4+(3+(2+1)))\\ & =& 5+(4+(3+3))\\ & =& 5+(4+6)\\ & =& 5+10\\ & =& 15\end{array}}$

def somme(n, s = 0) :
	if n == 0 : return s
	else : return  somme(n-1, s + n)
	
	
print(somme(5))

Fonctionnement :

1. Appel initial : somme(5). Le second paramètre (c'est à dire le paramètre s ) n'ayant pas de valeur indiquée dans l'appel, il prend la valeur par défaut donnée dans l'entête de la fonction (c'est à dire la valeur 0). En d'autres termes, l'appel somme(5) est équivalent à l'appel somme(5,0).
2. somme(5) retourne somme(4, 0 + 5). Qui doit donc être évaluée par appel à la fonction somme.
3. somme(4,5) est exécutée et retourne somme(3, 5+4). Qui doit donc être évaluée par appel à la fonction somme.
4. somme(3,9) est exécutée et retourne somme(2, 9+3). Qui doit donc être évaluée par appel à la fonction somme.
5. somme(2,12) est exécutée et retourne somme(1, 12+2). Qui doit donc être évaluée par appel à la fonction somme.
6. somme(1,14) est exécutée et retourne somme(0, 14+1). Qui doit donc être évaluée par appel à la fonction somme.
7. somme(0,15) est exécutée et retourne 15.