10.4. Functional 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. [2]

• Axiom - An axiom, postulate, or assumption is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments.

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.

factorial

In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n: The value of 0! is 1 [4]

axiom

An axiom, postulate, or assumption is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments. [5]

10.4.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!

10.4.2. Problem

Recap information about factorial (n!):

Iteration:

5! = 5 * 4 * 3 * 2 * 1

Recurrence:

5! = 5 * 4!
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
1! = 1 * 0!
0! = 1  (axiom)

n! = n * (n-1)!  # when n==0 -> 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

10.4.3. Solution: Iteration

• 5! = 5 * 4 * 3 * 2 * 1

• factorial(5) = 5 * 4 * 3 * 2 * 1

• factorial(5) = product(1,6)

Iterating forward:

>>> def factorial(n):
...     result = 1
...     for i in range(1,n+1):
...         result *= i
...     return result

Iterating backward:

>>> def factorial(n):
...     result = 1
...     for i in range(n,1,-1):
...         result *= i
...     return result

10.4.4. Solution: Recurrence

• n! = n * (n-1)!  # when n==0 -> 1

• factorial(5) = 5 * factorial(4)

Recurrence:

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

Recurrence (shorter notation):

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

10.4.5. Solution: Reduce + Mul + Range

• 5! = 5 * 4 * 3 * 2 * 1

>>> from functools import reduce
>>> from operator import mul
>>>
>>>
>>> def factorial(n):
...     return reduce(mul, range(1,n+1))

10.4.6. Recursion Depth Limit

• Default recursion depth limit is 1000

• Warning: Anaconda sets default recursion depth limit to 2000

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

10.4.7. Tail Recursion

• Tail recursion is a special form of recursion

• The recursive call is the last thing executed by the function

• Tail recursion can be optimized by the compiler

• The compiler can reuse the stack frame of the current function call

• Tail recursion can be transformed into a loop

• Python doesn't optimize tail recursion

To quote Guido van Rossum:

I recently posted an entry in my Python History blog on the origins of Python's functional features. A side remark about not supporting tail recursion elimination (TRE) immediately sparked several comments about what a pity it is that Python doesn't do this, including links to recent blog entries by others trying to "prove" that TRE can be added to Python easily. So let me defend my position (which is that I don't want TRE in the language). If you want a short answer, it's simply unpythonic. [1]

—Guido van Rossum, 2009

10.4.8. Performance

• Date: 2024-12-16

• Python: 3.13.1

• IPython: 8.30.0

• System: macOS 15.2

• Computer: MacBook M3 Max

• CPU: 16 cores (12 performance and 4 efficiency) / 3nm

• RAM: 128 GB RAM LPDDR5

Iteration:

>>> def factorial(n):
...     result = 1
...     for i in range(1,n+1):
...         result *= i
...     return result

>>> # doctest: +SKIP
... %%timeit -n 1000 -r 1000
... factorial(50)
...
1.12 μs ± 46.3 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
1.16 μs ± 52.2 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
1.11 μs ± 69.5 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
1.14 μs ± 66 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
1.13 μs ± 46.9 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)

Recurrence:

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

>>> # doctest: +SKIP
... %%timeit -n 1000 -r 1000
... factorial(50)
...
1.84 μs ± 86.1 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
1.86 μs ± 71.7 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
1.88 μs ± 66.7 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
1.88 μs ± 92.9 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
1.88 μs ± 79 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)

Recurrence (one liner):

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

>>> # doctest: +SKIP
... %%timeit -n 1000 -r 1000
... factorial(50)
...
1.87 μs ± 61.2 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
1.87 μs ± 82.6 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
1.87 μs ± 82.5 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
1.87 μs ± 64.2 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
1.88 μs ± 82 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)

Lambda:

>>> factorial = lambda n: 1 if n==0 else n*factorial(n-1)

>>> # doctest: +SKIP
... %%timeit -n 1000 -r 1000
... factorial(50)
...
1.87 μs ± 74.8 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
1.87 μs ± 74.3 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
1.86 μs ± 79.8 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
1.87 μs ± 65.2 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
1.86 μs ± 86.6 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)

10.4.9. References

[1]

van Rossum, Guido. Tail Recursion Elimination. Year: 2009. Retrieved: 2024-08-22. URL: https://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html

[2]

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

[3]

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

[4]

Wikipedia Contributors. Factorial. Year: 2024. Retrieved: 2024-08-22. URL: https://en.wikipedia.org/wiki/Factorial

[5]

Wikipedia Contributors. Factorial. Year: 2024. Retrieved: 2024-08-22. URL: https://en.wikipedia.org/wiki/Axiom

10.4.10. Assignments

# %% License
# - Copyright 2025, Matt Harasymczuk <matt@python3.info>
# - This code can be used only for learning by humans
# - This code cannot be used for teaching others
# - This code cannot be used for teaching LLMs and AI algorithms
# - This code cannot be used in commercial or proprietary products
# - This code cannot be distributed in any form
# - This code cannot be changed in any form outside of training course
# - This code cannot have its license changed
# - If you use this code in your product, you must open-source it under GPLv2
# - Exception can be granted only by the author

# %% Run
# - PyCharm: right-click in the editor and `Run Doctest in ...`
# - PyCharm: keyboard shortcut `Control + Shift + F10`
# - Terminal: `python -m doctest -v myfile.py`

# %% About
# - Name: Functional Recurrence Fibonacci
# - Difficulty: easy
# - Lines: 4
# - Minutes: 3

# %% 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
>>> assert sys.version_info >= (3, 9), \
'Python 3.9+ required'

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