# Уређивање

def каскада(n):
    """Исписује каскаду префикса природног броја n.

    >>> каскада(1234)
    1234
    123
    12
    1
    12
    123
    1234
    """
    if n < 10:
        print(n)
    else:
        print(n)
        каскада(n//10)
        print(n)

def алтернативнаКаскада(n):
    """Исписује каскаду префикса природног броја n."""
    print(n)
    if n >= 10:
        алтернативнаКаскада(n//10)
        print(n)

def инверзна_каскада(n):
    """Исписује инверзну каскаду префикса природног броја n.

    >>> инверзна_каскада(1234)
    1
    12
    123
    1234
    123
    12
    1
    """
    расте(n)
    print(n)
    опада(n)

def f_па_g(f, g, n):
    if n:
        f(n)
        g(n)

расте = lambda n: f_па_g(расте, print, n//10)
опада = lambda n: f_па_g(print, опада, n//10)

# Стабло рекурзије

def фиб(n):
    """Израчунава n-ти Фибоначијев број.

    >>> фиб(8)
    21
    """
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return фиб(n-2) + фиб(n-1)

def број_партиција(n, m):
    """Броји партиције од n користећи се сабирцима мањим или једнаким m.

    >>> број_партиција(6, 4)
    9
    >>> број_партиција(10, 10)
    42
    """
    if n == 0:
        return 1
    elif n < 0:
        return 0
    elif m == 0:
        return 0
    else:
        са_m = број_партиција(n-m, m)
        без_m = број_партиција(n, m-1)
        return са_m + без_m

# Ханојска кула
def потез(број_диска, почетни_штап, крајњи_штап):
    print('Преместити диск ' + str(број_диска) + \
          ' са ' + str(почетни_штап) + ' на ' + str(крајњи_штап) + '.')

def ханојска_кула(n, почетни, крајњи, помоћни):
    """Решава Ханојску кулу са n дискова и исписује решење.

    >>> ханојска_кула(3, 'X', 'Y', 'Z')
    Преместити диск 1 са X на Y.
    Преместити диск 2 са X на Z.
    Преместити диск 1 са Y на Z.
    Преместити диск 3 са X на Y.
    Преместити диск 1 са Z на X.
    Преместити диск 2 са Z на Y.
    Преместити диск 1 са X на Y.
    """
    if n == 1:
        потез(n, почетни, крајњи)
    else:
        ханојска_кула(n-1, почетни, помоћни, крајњи)
        потез(n, почетни, крајњи)
        ханојска_кула(n-1, помоћни, крајњи, почетни)
