Aller au contenu

Algos récursif 🔂⚓︎

Factorielle récursive⚓︎

Factorielle récursive
🐍 Script Python
1
2
3
4
5
def factorielle(n):
    if n == 1:
        return 1
    else:
        return n * factorielle(n - 1)

PGCD récursif⚓︎

PGCD récursif
🐍 Script Python
1
2
3
4
5
def pgcd(a, b):
    if b == 0:
        return a
    else:
        return pgcd(b, a%b)

Puissance récursive (simple)⚓︎

Puissance récursive
🐍 Script Python
1
2
3
4
5
def puissance(x, n):
    if n == 0:
        return 1
    else:
        return x * puissance(x, n-1)

Puissance récursive (optimisée)⚓︎

Puissance récursive
🐍 Script Python
1
2
3
4
5
6
7
8
def puissance(x, n):
    if n == 0:
        return 1
    else:
        if n % 2 == 0:
            return puissance(x*x, n//2)
        else :
            return x*puissance(x*x, (n-1)//2)

Recherche dichotomique récursive (avec slicing)⚓︎

Note : le slicing de liste n'est pas au programme de NSI.

Recherche dichotomique récursive
🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def recherche(lst, m):
    if len(lst) == 1: 
        if lst[0] == m:
            return True
        else :
            return False
    else:              
        mid = len(lst)//2
        if lst[mid] > m:
            return recherche(lst[:mid], m)
        else :
            return recherche(lst[mid:], m)