Rekurzija

Začetna vaje iz rekurzije

Babuške

Imejmo poljubno celo število v seznamu v seznamu v seznamu ... v seznamu, poljubno mnogokrat. Takšni strukturi bomo rekli babuška. Primeri babušk so 13, [473], [[[[21]]]], [[7]], itd.

1. podnaloga

Sestavi funkcijo babuska(par), ki za parameter dobi takšno babuško ter vrne število seznamov, v katere je zaprto celo število. Za zgornje primere so rezultati 0, 1, 4 in 2. Predpostavi, da je struktura pravilna, torej res opisana kot zgoraj!

Uradna rešitev

def babuska(mojaB):
    '''Vrne število seznamov, v katere je zaprto celo število '''
    if isinstance(mojaB, int) : # ustavitveni pogoj - opraviti imamo s celim številom
        return 0
    # imamo torej vsaj eno zunanjo lupino
    znotraj = mojaB[0]     # odluščimo
    # in preštejemo koliko jih je znotraj
    koliko = babuska(znotraj)
    return 1 + koliko

2. podnaloga

Sestavi funkcijo kdoSeSkriva(par), ki za parameter dobi takšno babuško ter vrne zaprto celo število. Predpostavi, da je struktura pravilna, torej res opisana kot zgoraj! Pri reševanju boste morali preveriti, kakšnega tipa je podatek. V ta namen v ukazni lupini preizkusite naslednje ukaze:

   isinstance(12, int)
   x = 3.5
   isinstance(x, float)
   isinstance(x, int)
   isinstance(x, (int, float))
   isinstance(3, str)
   isinstance("3", str)
   isinstance([], list)
   s = [2, [3]]
   isinstance(s, list)
   isinstance(s[0], list)
   isinstance(s[0], int)
   isinstance(s[1], int)
   isinstance(s[1], list)
   isinstance(s[1][0], int)

Uradna rešitev

def kdoSeSkriva(mojaB):
    '''Vrne število seznamov, v katere je zaprto celo število '''
    if isinstance(mojaB, int) : # število ni skrito!
        return mojaB
    # imamo torej vsaj eno zunanjo lupino
    znotraj = mojaB[0]     # odluščimo
    # in poglejmo, kaj je znotraj
    kdo = kdoSeSkriva(znotraj)
    return kdo

Dolžina niza

1. podnaloga

Napišite rekurzivno funkcijo dolzina, ki sprejme niz in izračuna njegovo dolžino. Niz je sestavljen samo iz črk in števk. Dolžino izračunajte po takšnem pravilu: vsaka števka k dolžini prispeva svojo vrednost, vsaka črka pa 1 (kot običajno).

Primeri:

>>> dolzina('5a')
6
>>> dolzina('abcde12345')
20

V funkciji ne smete uporabiti zanke while ali zanke for!

Pri ugotavljanju, ali gre za črko ali števko si pomagajte s funkcijama isalpha() in isdigit(). Na primer:

>>> 'a'.isalpha()
True
>>> '5'.isdigit()
True

Uradna rešitev

def dolzina(s):
    '''Izračun drugačne dolžine niza'''
    if s == "": 
        return 0
    # razbijemo na prvi znak in preostanek (rep)
    prviZnak = s[0]
    rep = s[1:]
    dolzinaRepa = dolzina(rep)
    # kako prištejemo prvi znak
    if prviZnak.isalpha():
        return 1 + dolzinaRepa
    elif prviZnak.isdigit():
        return int(prviZnak) + dolzinaRepa

def dolzinaV2(niz):
    '''vrne "dolzino" niza, kjer je dolžina def. nekoliko drugače'''
    if niz == '':
        return 0
    if len(niz) == 1 : # samo en znak v nizu
        if niz.isdigit() : # in to je števka
            return(int(niz))          
        return 1 # ni števka, je "navaden" znak
    # "dolzina" celega niza je "dolzina" niza, ki ga
    # sestavlja le prvi znak in "dolzine" preostanka
    
    return dolzina(niz[0]) + dolzina(niz[1:])

SSCČ

Seznam seznamov celih števil (SSCŠ) je seznam, katerega elementi so bodisi cela števila bodisi seznami seznamov celih števil. Da bo enostavneje, recimo, da je tudi prazen seznam SSCŠ. Nekaj primerov:

      [-1, 2, -3]
      [1, [2], 3, [2, 3, 4]]
      [[[[2]], 1], [2, [[-3], [4]]]]

1. podnaloga

Sestavi funkcijo prestejStevila(sscs), ki prešteje, koliko je v sscs celih števil. Za primere od zgoraj so rezultati:

      3
      6
      5

Uradna rešitev

def prestejStevila(sscs):
    if len(sscs) == 0 : # tudi prazen seznam je SSCS
        return 0 # in nima celih števil
    kolikoStevil = 0
    # pregledamo vse elemente
    for el in sscs :
        # če je element 'običajno število'
        if isinstance(el, int):
            kolikoStevil += 1
        else : # potem mora pa biti sscs in moramo prešteti vsa cela števila v njem
            kolikoVSSCS = prestejStevila(el)
            kolikoStevil += kolikoVSSCS
    return kolikoStevil

2. podnaloga

Sestavi funkcijo prestejNegativnaStevila(sscs), ki prešteje, koliko je v seznamu seznamov negativnih celih števil. Za primere od zgoraj so rezultati:

      2
      0
      1

Uradna rešitev

def prestejNegativnaStevila(sscs):
    if len(sscs) == 0 : # tudi prazen seznam je SSCS
        return 0 # in nima celih števil
    kolikoStevil = 0
    # pregledamo vse elemente
    for el in sscs :
        # če je elemnt 'običajno število'
        if isinstance(el, int):
            if el < 0: # če je negativen, povečamo števec, drugače nič!
                kolikoStevil += 1
        else : # potem mora pa biti sscs in moramo prešteti vsa neg. cela števila v njem
            kolikoVSSCS = prestejNegativnaStevila(el)
            kolikoStevil += kolikoVSSCS
    return kolikoStevil

3. podnaloga

Sestavi funkcijo sestejStevila(sscs), ki sešteje vsa cela števila v seznamu seznamov celih števil. Za primere od zgoraj so rezultati:

      -2
      15
      6

Uradna rešitev

def sestejStevila(sscs):
    if len(sscs) == 0 : # tudi prazen seznam je SSCS
        return 0 # z vsoto 0
    vsotaStevil = 0
    # pregledamo vse elemente
    for el in sscs :
        # če je element 'običajno število'
        if isinstance(el, int):
            vsotaStevil += el # ga dodamo vsoti
        else : # če ni, pa mora biti sscs in njegovo vsoto dodamo skupni
            vsotaTegaEl = sestejStevila(el)
            vsotaStevil += vsotaTegaEl
    return vsotaStevil

4. podnaloga

Sestavi funkcijo jeSSCS(sscs), ki preveri (vrne True oz. False), če je dan seznam res seznam seznamov celih števil.

Uradna rešitev

def jeSSCS(sscs):
    if not isinstance(sscs, list): # če sploh ne gre za seznam
        return False
    if len(sscs) == 0 : # tudi prazen seznam je SSCS
        return True 
    # pregledamo vse elemente
    for el in sscs :
        # če je element ni ne SSCS ne celo število
        if not isinstance(el, int) and  \
           not jeSSCS(el) : # ne SSCE
            return False
    # vsi testi OK       

    return True

5. podnaloga

Sestavi funkcijo splosci(sscs), ki "splošči" seznam seznamov celih števil, torej vrne navaden seznam celih števil, ki so vsebovana v SSCŠ (v istem vrstnem redu). Za primere od zgoraj so rezultati:

      [-1, 2, -3]
      [1, 2, 3, 2, 3, 4]
      [2, 1, 2, -3, 4]

Uradna rešitev

def splosci(sscs):
    if len(sscs) == 0 : # prazen seznam je SSCS
        return [] # in vrnemo enakega
    noviSez = []
    # pregledamo vse elemente
    for el in sscs :
        # če je element 'običajno število'
        if isinstance(el, int):
                noviSez.append(el) # ga dodamo seznamu
        else : # če ni, pa mora biti sscs in dodamo sploščeno različico
            splosceniDel = splosci(el)
            noviSez.extend(splosceniDel)
    return noviSez