Récursivité en Python
MéthodePrincipe :
def f(n):
if n == 0: # cas de base
return 1
return n * f(n-1) # appel récursif
EXEMPLES CLASSIQUES :
def factorielle(n):
if n<=1: return 1
return n*factorielle(n-1)
def fibo(n):
if n<=1: return n
return fibo(n-1)+fibo(n-2) # O(2ⁿ) naïf !
Fibo avec mémoïsation (O(n)) :
from functools import lru_cache
@lru_cache
def fibo(n):
if n<=1: return n
return fibo(n-1)+fibo(n-2)
⚡ Toute récursion doit avoir un CAS DE BASE (terminaison) sinon RecursionError. Python limite la récursion à ~1000 niveaux.
Matrices 2D et algorithmes
MéthodeMatrice n×p :
M = [[0]*p for _ in range(n)]
M[i][j] = valeur
Produit matriciel :
def produit(A, B):
n,p,q = len(A),len(B),len(B[0])
C = [[sum(A[i][k]*B[k][j] for k in range(p))
for j in range(q)] for i in range(n)]
return C
RECHERCHE DICHOTOMIQUE :
def dicho(lst, val):
g, d = 0, len(lst)-1
while g <= d:
m = (g+d)//2
if lst[m]==val: return m
elif lst[m]<val: g=m+1
else: d=m-1
return -1