# 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¶

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.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():
...