8.6. Function Recurrence

Aby zrozumieć rekurencję – 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

  • Uncontrolled recursion causes stack overflows!

  • Rewriting the algorithm iteratively, is generally a better idea

8.6.2. Example

Recap information about factorial (n!):

5! = 5 * 4!
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
1! = 1 * 0!
0! = 1

>>> 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. Use Case

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

Figure 8.1. Hanoi Tower as a standard example of a recurrence. Source: 1

8.6.4. 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.5. Assignments

Code 8.16. Solution
"""
* Assignment: Function Recurrence Fibonacci
* Filename: function_recurrence_fibonacci.py
* Complexity: easy
* Lines of code: 5 lines
* Time: 8 min

English:
    1. Fibonacci series is created by adding two previous numbers, i.e.:
        1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
    2. Define function `fib(n)` using recursion to generate items of the Fibonacci series
    3. For `n` less or equal to 0, return 1
    4. Else return sum `fib(n-1)` and `fib(n-2)`

Polish:
    1. Ciąg Fibonacciego powstaje przez dodawanie dwóch poprzednich liczb, np:
        1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
    2. Zdefiniuj funkcję `fib(n)` używającą rekurencji do generowania wyrazów ciągu Fibonacciego
    3. Dla `n` mniejszej lub równej 0, zwróć 1
    4. W przeciwnym wypadku zwróć sumę `fib(n-1)` i `fib(n-2)`

Tests:
    >>> fib(1)
    1
    >>> fib(2)
    2
    >>> fib(5)
    8
    >>> fib(9)
    55
    >>> fib(10)
    89
    >>> [fib(x) for x in range(10)]
    [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
"""
Code 8.17. Solution
"""
* Assignment: Function Recurrence Brackets
* Filename: function_recurrence_brackets.py
* Complexity: medium
* Lines of code: 10 lines
* Time: 21 min

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:
        a. round: `(` i `)`
        b. square: `[` i `]`
        c. curly `{` i `}`
        d. 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:
        a. okrągłe: `(` i `)`
        b. kwadratowe: `[` i `]`
        c. klamrowe `{` i `}`
        d. trójkątne `<` i `>`

Tests:
    >>> from inspect import isfunction
    >>> isfunction(is_bracket_balanced)
    True
    >>> 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
"""


# Given
BRACKET_OPEN = ('(', '{', '[', '<')
BRACKET_CLOSE = (')', '}', ']', '>')
PAIRS = dict(zip(BRACKET_OPEN, BRACKET_CLOSE))