Exempel på rekursion

Tre exempel på rekursiva funktioner

def fakultet(n):
    if n == 0 : return 1
    else : 
        return n*fakultet(n-1)
 
def artitmetisk_summa(n, d):
    if n == 0 : return 0
    else : return n*d+artitmetisk_summa(n-1, d)
    
   
def binar_sokning(a, l, min, max):
    if l[max] == a : i=max
    else :
        mitt = (min+max) // 2
        if a > l[mitt] : i=binar_sokning(a,l, mitt, max)
        else : i=binar_sokning(a,l, min, mitt)
    return i

print("Fakultet " + str(fakultet(5)))
print("Summa " + str(artitmetisk_summa(4, 2)))
lista=[1, 3, 5, 8, 9, 10, 12, 16]
print("Sökning " + str(binar_sokning(16, lista, 0, 7)))

En rekursiv funktion kallar på sig själv tills ett begränsande villkor är uppfyllt. Fakultetsberäkningen ovan kan beskrivas med denna bild:

 

Först byggs stacken av funktionsanrop upp tills fakultet(0) returnerar 1. När detta sker vänder det och stacken krymper då varje steg returnerar sina värden. Slutligen returnerar fakultet(5) sitt värde till print som skriver ut det.

Uppgift 3.3
Skriv och testa en rekursiv funktion för att beräkna en geometrisk summa. (Du kan använda ** för upphöjt i Python.)