# Стабла

def стабло(ознака, гране=[]):
    for грана in гране:
        assert да_ли_је_стабло(грана), 'гране морају бити стабла'
    return [ознака] + list(гране)

def ознака(стабло):
    return стабло[0]

def гране(стабло):
    return стабло[1:]

def да_ли_је_стабло(стабло):
    if type(стабло) != list or len(стабло) < 1:
        return False
    for грана in гране(стабло):
        if not да_ли_је_стабло(грана):
            return False
    return True

def да_ли_је_лист(стабло):
    return not гране(стабло)

### +++ === АПСТРАКЦИЈСКА БАРИЈЕРА === +++ ###

def фиб_стабло(n):
    """Прави Фибоначијево стабло.

    >>> фиб_стабло(1)
    [1]
    >>> фиб_стабло(3)
    [2, [1], [1, [0], [1]]]
    >>> фиб_стабло(5)
    [5, [2, [1], [1, [0], [1]]], [3, [1, [0], [1]], [2, [1], [1, [0], [1]]]]]
    """
    if n == 0 or n == 1:
        return стабло(n)
    else:
        лево = фиб_стабло(n-2)
        десно = фиб_стабло(n-1)
        фиб_n = ознака(лево) + ознака(десно)
        return стабло(фиб_n, [лево, десно])

def број_листова(стабло):
    """Враћа укупан број листова у стаблу.

    >>> број_листова(фиб_стабло(5))
    8
    """
    if да_ли_је_лист(стабло):
        return 1
    else:
        return sum([број_листова(г) for г in гране(стабло)])

def листови(стабло):
    """Враћа низ ознака свих листова у задатом стаблу.

    >>> листови(фиб_стабло(5))
    [1, 0, 1, 0, 1, 1, 0, 1]
    """
    if да_ли_је_лист(стабло):
        return [ознака(стабло)]
    else:
        return sum([листови(г) for г in гране(стабло)], [])

def print_ознаке(с):
    """Исписује чворове стабла, сваку ознаку у новом реду.
    >>> print_ознаке(стабло(3))
    3
    >>> print_ознаке(стабло(2, [стабло(1)]))
    2
    1
    >>> print_ознаке(фиб_стабло(4))
    3
    1
    0
    1
    2
    1
    1
    0
    1
    """
    print(ознака(с))
    for г in гране(с):
        print_ознаке(г)

def print_стабло(с, дубина=0):
    """Исписује репрезентацију стабла у коме је свака ознака
       увучена са два размака помножена са дубином од корена.

    >>> print_стабло(стабло(1))
    1
    >>> print_стабло(стабло(1, [стабло(2)]))
    1
      2
    >>> print_стабло(фиб_стабло(4))
    3
      1
        0
        1
      2
        1
        1
          0
          1
    """
    print('  ' * дубина + str(ознака(с)))
    for г in гране(с):
        print_стабло(г, дубина + 1)

def увећај_листове(с):
    """Враћа стабло као с са увећаним ознакама свих листова.

    >>> print_стабло(увећај_листове(фиб_стабло(4)))
    3
      1
        1
        2
      2
        2
        1
          1
          2
    """
    if да_ли_је_лист(с):
        return стабло(ознака(с) + 1)
    else:
        грне = [увећај_листове(г) for г in гране(с)]
        return стабло(ознака(с), грне)

def увећај_листове_мутацијом(с):
    """Увећава ознаке свих листова стабла мутацијом стабла.

    >>> фс4 = фиб_стабло(4)
    >>> увећај_листове_мутацијом(фс4)
    >>> print_стабло(фс4)
    3
      1
        1
        2
      2
        2
        1
          1
          2
    """
    if да_ли_је_лист(с):
        с[0] = с[0] + 1
    else:
        for г in гране(с):
            увећај_листове_мутацијом(г)

def увећај(с):
    """Враћа стабло као с са увећаним свим ознакама.

    >>> print_стабло(увећај(фиб_стабло(4)))
    4
      2
        1
        2
      3
        2
        2
          1
          2
    """
    return стабло(ознака(с) + 1, [увећај(г) for г in гране(с)])

def увећај_мутацијом(с):
    """Увећава све ознаке стабла мутацијом стабла.

    >>> фс4 = фиб_стабло(4)
    >>> увећај_мутацијом(фс4)
    >>> print_стабло(фс4)
    4
      2
        1
        2
      3
        2
        2
          1
          2
    """
    с[0] += 1
    for г in гране(с):
        увећај_мутацијом(г)

# Редослед

def факт(n):
    """Враћа n * n-1 * ... * 1.

    >>> факт(4)
    24
    """
    if n == 0:
        return 1
    else:
        return n * факт(n - 1)

def факт_реп(n):
    """Враћа n * n-1 * ... * 1.

    >>> факт_реп(4)
    24
    """
    return факт_пута(n, 1)

def факт_пута(n, k=1):
    """Враћа k * n * n-1 * ... * 1.

    >>> факт_пута(4, 3)
    72
    """
    if n == 0:
        return k
    else:
        return факт_пута(n - 1, k * n)

журба = стабло('ж', [стабло('у', [стабло('р'), стабло('б')]), стабло('а')])

def print_збирови(с, збир_путање):
    """Исписује збирове ознака на путањама од корена до сваког листа.

    >>> print_збирови(стабло(3, [стабло(4), стабло(5, [стабло(6)])]), 0)
    7
    14
    >>> print_збирови(журба, '')
    жур
    жуб
    жа
    """
    збир_путање = збир_путање + ознака(с)
    if да_ли_је_лист(с):
        print(збир_путање)
    else:
        for грана in гране(с):
            print_збирови(грана, збир_путање)

def изброј_путање(с, збир):
    """Враћа број путања од корена до ма ког чвора у с
       за које је збир ознака на путањи једнак збиру.

    >>> с = стабло(3, [стабло(-1), стабло(1, [стабло(2, [стабло(1)]), стабло(3)]), стабло(1, [стабло(-1)])])
    >>> print_стабло(с)
    3
      -1
      1
        2
          1
        3
      1
        -1
    >>> изброј_путање(с, 3)
    2
    >>> изброј_путање(с, 4)
    2
    >>> изброј_путање(с, 5)
    0
    >>> изброј_путање(с, 6)
    1
    >>> изброј_путање(с, 7)
    2
    """
    if ознака(с) == збир:
        нађена = 1
    else:
        нађена = 0
    return нађена + sum([изброј_путање(г, збир - ознака(с)) for г in гране(с)])
