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.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¶
"""
* 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]
"""
"""
* 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))