8.6. Function Recurrence

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

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

8.6.1. Rationale

  • 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

../../_images/function-recurrence-hanoi.jpg

Figure 8.1. Hanoi Tower as a standard example of a recurrence. Source: [hanoi]

8.6.2. Example

def factorial(n):
    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

8.6.3. Recursion Depth Limit

  • Default recursion depth limit is 1000

  • Warning: Anaconda sets default recursion depth limit to 2000

import sys

sys.setrecursionlimit(3000)

8.6.4. Assignments

8.6.4.1. Function Recurrence 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