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)
Listing 8.20. Recap information about factorial (n!)
"""
5! = 5 * 4!
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
1! = 1 * 0!
0! = 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

  • Assignment name: Function Recurrence Brackets

  • Last update: 2020-10-01

  • Complexity level: medium

  • Lines of code to write: 10 lines

  • Estimated time of completion: 21 min

  • Solution: solution/function_recurrence_brackets.py

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