4.5. FuncProg Recurrence

  • 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. 1

Aby zrozumieć rekurencję – musisz najpierw zrozumieć rekurencję.

In order to understand recursion, you must understand recursion. 3

In the functional programming paradigm, there are no for and while loops. Instead, these languages rely on recursion for iteration. Recursion is implemented using recursive functions, which call themselves repeatedly until the base case is reached.

4.5.1. 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

  • Rewriting the algorithm iteratively, is generally a better idea

  • Uncontrolled recursion causes stack overflows!

4.5.2. Example

Recap information about factorial (n!):

5! = 5 * 4!
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
1! = 1 * 0!
0! = 1
n! = n * (n-1)!  # 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

4.5.3. Recursion Depth Limit

  • Default recursion depth limit is 1000

  • Warning: Anaconda sets default recursion depth limit to 2000

>>> import sys
>>>
>>> sys.setrecursionlimit(3000)

4.5.4. Use Case - 0x01

../../_images/funcprog-recurrence-hanoi.jpg

Figure 4.4. Hanoi Tower as a standard example of a recurrence. Source: 2

4.5.5. Use Case - 0x02

>>> def factorial(n):
...     if n == 0:
...         return 1
...     return n * factorial(n-1)
>>> def factorial(n):
...     return 1 if n == 0 else n * factorial(n-1)
>>> def factorial(n):
...     return n * factorial(n-1) if n else 1

4.5.6. Use Case - 0x03

>>> CACHE = {}
>>>
>>> def factorial(n):
...     if n not in CACHE:
...         CACHE[n] = n * factorial(n-1) if n else 1
...     return CACHE[n]
>>> factorial(5)
120
>>>
>>> factorial(6)
720
>>>
>>> CACHE
{0: 1, 1: 1, 2: 2, 3: 6, 4: 24, 5: 120, 6: 720}
>>> factorial(5)
120
>>>
>>> CACHE[5]
120
>>>
>>> 5 * CACHE[4]
120

4.5.7. References

1

Functional programming. Retrieved: 2020-10-09. URL: https://en.wikipedia.org/wiki/Functional_programming

2

https://dyermath.files.wordpress.com/2015/06/hanoi-13.jpg

3

Hunter, David (2011). Essentials of Discrete Mathematics. Jones and Bartlett. p. 494. ISBN 9781449604424.

4.5.8. Assignments

Code 4.27. Solution
"""
* Assignment: FuncProg Recurrence Fibonacci
* Required: yes
* Complexity: easy
* Lines of code: 4 lines
* Time: 3 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]
"""


# Use recursion to add two previous numbers;
# For `n` less or equal to 1, return 1;
# Else return sum `fib(n-1)` and `fib(n-2)`
# type: Callable[[int], int]
def fib():
    ...