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

• Complexity level: medium

• Lines of code to write: 10 lines

• Estimated time of completion: 15 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:

• 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