Naloge

Obrni seznam

Napišite rekurzivno funkcijo obrni(xs), ki obrne seznam. Na primer, klic obrni([1, 2, 3, 4, 5]) mora vrniti seznam [5, 4, 3, 2, 1].

def obrni(xs):
    if not xs:
        return []
    return obrni(xs[1:]) + [xs[0]]

Dolžina seznama

Napišite rekurzivno funkcijo dolzina(xs), ki vrne dolžino seznama. Na primer, klic funkcije dolzina([1, 2, 3, 4,]) vrne vrednost 4.

def dolzina(xs):
    if not xs:
        return 0
    return dolzina(xs[1:]) + 1

Iskanje elementa

Napiši rekurzivno funkcijo vsebuje(s, x), ki pove, ali seznam s vsebuje element x. V primeru, da s vsebuje element x funkcije vrne True drugače pa False.

Seznam vsebuje element x, če s ni prazen in je bodisi prvi element s enak x, bodisi ostanek seznama vsebuje x.

def vsebuje(s, x):
    if not s:
        return False
    return s[0] == x or vsebuje(s[1:], x)

Najmanjša vrednost

Napišite rekurzivno funkcijo najmanjsa(xs), ki vrne najmanjšo vrednost v seznamu xs. Klic funkcije najmanjsa([5, 2, 2, -1, 3]) naj vrne -1.

Najmanjšo vrednost v seznamu dobimo tako, da izberemo manjšo izmed prve vrednosti v seznamu in najmanšo vrednostjo v preostanku seznama.

def najmanjsa(xs):
    if len(xs) == 1:
        return xs[0]
    return min(xs[0], najmanjsa(xs[1:]))

Enaka seznama

Napiši rekurzivno funkcijo enaka(s, t), ki pove (s True ali False) ali sta dva seznama enaka ali ne. Dva seznama sta enaka, če sta oba prazna ali pa sta oba neprazna in imata enaka prva elementa in sta enaka tudi ostanka seznama (vse razen prvega elementa).

Pri tej nalogi predvidite, da bosta seznama vedno enako dolga. Tisti, ki pa ste za dodaten izziv pa jo sprogramirajte tako, da deluje tudi v primeru, ko sta seznama različno dolga (pri tem ne uporabite funkcije len za primerjavo dolžin).

def enaka(s, t):
    if not s and not t:
        return True
    return s[0] == t[0] and enaka(s[1:], t[1:])

Naraščajoči seznam

Napišite rekurzivno funkcijo narascajoci(s), ki vrne True, če je podani seznam naraščajoč, in False, če ni.

Seznam je naraščajoč, če je prvi element manjši od drugega in če je naraščajoč tudi seznam od drugega elementa naprej. Poleg tega so seveda naraščajoči vsi seznami z manj kot dvema elementoma.

def narascajoci(s):
    if len(s) < 2:
        return True
    return s[0] < s[1] and narascajoci(s[1:])

Največji skupni delitelj

Napiši funkcijo gcd(a, b), ki izračuna največji skupni delitelj števil a in b. Na primer, največji skupni delitelj števil 8 in 12 je 4.

Največji skupni delitelj bom računali z Evklidovim alogoritmom, ki je v primeru, da sta a in b oba pozitivna, definiran takole:

gcd(a,a) = a,
gcd(a,b) = gcd(a-b, b); če je a > b
gcd(a,b) = gcd(a, b-a);  če je b > a

Torej v primeru, da sta a in b enaki števili, je največji skupni delitelj kar a. V primeru, da je a večji kot b, največji skupni delitelj najdemo tako, da izračunamo največjega skupnega delitelja števil a-b in b. V primeru, da je b večji od a, pa dobimo največjega skupnega delitelja tako, da izračunamo največji skupni delitej števil a in b-a.

def gcd(a, b):
    if a == b:
        return a
    elif a > b:
        return gcd(a-b, b)
    else:  # a < b
        return gcd(a, b-a)

Fakulteta

Napišite funkcijo fakulteta(x), ki na rekurzivni način izračuna fakulteto števila x.

Fakulteto n! navadno računamo kot produkt n števil; 5! = 1*2*3*4*5. Lahko pa bi jo definirali tudi takole: n! = n (n – 1)! Če jo lahko tako definiramo - pa jo tako še sprogramirajmo!

Da se stvar izteče, se moramo dogovoriti še, da je 0! enako 1.

def fakulteta(n):
    if n == 0:
        return 1
    return n*fakulteta(n-1)

Preverjanje Fibonacija

Zaporedje je Fibonacijevo, če je vsak člen enak vsoti prejšnjih dveh.

Seznam vsebuje Fibonacijevo zaporedje, če ima manj kot tri elemente ALI pa je zadnji element vsota predzadnjih dveh in je tudi seznam brez zadnjega elementa Fibonacijev.

Napiši rekurzivno funkcijo je_fibo(s), ki preveri, ali podani seznam vsebuje Fibonacijevo zaporedje.

Primer seznama, ki vsebuje Fibonacijevo zaporedje: [1, 1, 2, 3, 5, 8, 13].

def je_fibo(s):
    if len(s) < 3:
        return True
    return s[-3] + s[-2] == s[-1] and je_fibo(s[:-1])

Zadnje liho

Napiši rekurzivno funkcijo zadnje_liho(s), ki vrne zadnje liho število v podanem seznamu ali None, če v njem ni lihih števil.

def zadnje_liho(s):
    if not s:
        return None
    if s[-1] % 2 == 1:
        return s[-1]
    return zadnje_liho(s[:-1])