12.6. Function Recurrence¶
Aby zrozumieć rekurencję – musisz najpierw zrozumieć rekurencję.
12.6.1. Rationale¶
Also known as recursion
Iteration in functional languages is usually accomplished via recursion
Recursive functions invoke themselves
Operation is repeated until it reaches the base case
In general, recursion requires maintaining a stack, which consumes space in a linear amount to the depth of recursion.
This could make recursion prohibitively expensive to use instead of imperative loops.
However, a special form of recursion known as tail recursion can be recognized and optimized by a compiler into the same code used to implement iteration in imperative languages.
Tail recursion optimization can be implemented by transforming the program into continuation passing style during compiling, among other approaches. [#WikipediaFunc]_
12.6.2. Recurrence in Python¶
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
12.6.3. 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
12.6.4. Use Case¶
Figure 12.1. Hanoi Tower as a standard example of a recurrence. Source: 1¶
12.6.5. Recursion Depth Limit¶
Default recursion depth limit is 1000
Warning: Anaconda sets default recursion depth limit to 2000
>>> import sys
>>>
>>> sys.setrecursionlimit(3000)
12.6.6. Assignments¶
"""
* Assignment: Function Recurrence Fibonacci
* Required: no
* 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 1, return 1
4. Else return sum `fib(n-1)` and `fib(n-2)`
5. Run doctests - all must succeed
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 1, zwróć 1
4. W przeciwnym wypadku zwróć sumę `fib(n-1)` i `fib(n-2)`
5. Uruchom doctesty - wszystkie muszą się powieść
Tests:
>>> import sys; sys.tracebacklimit = 0
>>> 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]
"""
