9.6. Function Recurrence

Aby zrozumieć rekurencję – musisz najpierw zrozumieć rekursję. Aby zrozumieć rekursję - musisz najpierw zrozumieć rekurencję.

9.6.1. What is recurrence?

  • Also known as recursion

  • Python isn't a functional language

  • CPython implementation doesn't optimize tail recursion

  • Tail recursion is not a particularly efficient technique in Python

  • Unbridled recursion causes stack overflows!

  • Rewriting the algorithm iteratively, is generally a better idea

def factorial(n: int) -> int:
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)
factorial(5)                                    # = 120
    return 5 * factorial(4)                     # 5 * 24 = 120
        return 4 * factorial(3)                 # 4 * 6 = 24
            return 3 * factorial(2)             # 3 * 2 = 6
                return 2 * factorial(1)         # 2 * 1 = 2
                    return 1 * factorial(0)     # 1 * 1 = 1
                        return 1                # 1

9.6.2. Limit

  • Default recursion depth limit is 1000

  • Warning: Anaconda sets default recursion depth limit to 2000

import sys

sys.setrecursionlimit(3000)

9.6.3. Assignments

9.6.3.1. Balanced Brackets

English
  1. Create function which checks if brackets are balanced

  2. Brackets are balanced, when each opening bracket has closing pair

  3. Use recursion

  4. Types of brackets:

    • round: ( i )

    • square: [ i ]

    • curly { i }

    • angle < i >

Polish
  1. Stwórz funkcję, która sprawdzi czy nawiasy są zbalansowane

  2. Nawiasy są zbalansowane, gdy każdy otwierany nawias ma zamykającą parę

  3. Użyj rekurencji

  4. Typy nawiasów:

    • okrągłe: ( i )

    • kwadratowe: [ i ]

    • klamrowe { i }

    • trójkątne < i >

def is_bracket_balanced(text: str) -> bool:
    """
    >>> is_bracket_balanced('{}')
    True
    >>> is_bracket_balanced('()')
    True
    >>> is_bracket_balanced('[]')
    True
    >>> is_bracket_balanced('<>')
    True
    >>> is_bracket_balanced('')
    True
    >>> is_bracket_balanced('(')
    False
    >>> is_bracket_balanced('}')
    False
    >>> is_bracket_balanced('(]')
    False
    >>> is_bracket_balanced('([)')
    False
    >>> is_bracket_balanced('[()')
    False
    >>> is_bracket_balanced('{()[]}')
    True
    >>> is_bracket_balanced('() [] () ([]()[])')
    True
    >>> is_bracket_balanced("( (] ([)]")
    False
    """
    pass