A quick introduction
L2L Warszawa 2017
Sławomir Śledź
Senior Java Developer
Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem.
I will focus on recursion in the context of computation
Informal definition says that recursive procedure is a procedure which calls itself.
Can be defined by two properties:
A procedure is a set of steps based on a set of rules. (step-by-step description of the process)
A process is a running of procedure, involving following the rules and performing the steps. (activity)
n! = n * (n - 1) * (n - 2)...3 * 2 * 1
def factorial(n):
if n == 1 or n == 0:
return 1
return n * factorial(n - 1)
(factorial 6)
(6 * (factorial 5))
(6 * (5 * (factorial 4)))
(6 * (5 * (4 * (factorial 3))))
(6 * (5 * (4 * (3 * (factorial 2)))))
(6 * (5 * (4 * (3 * (2 * (factorial 1))))))
(6 * (5 * (4 * (3 * (2 * 1)))))
(6 * (5 * (4 * (3 * 2))))
(6 * (5 * (4 * 6)))
(6 * (5 * 24))
(6 * 120)
720
Such process is called recursive process
When the length of deferred operations is increasing proportional to the arguments then such process is called 'linear recursive process'
def factorial(n):
def fact_iter(product, counter, max_count):
if counter > max_count:
return product
return fact_iter(counter * product, counter + 1, max_count)
return fact_iter(1, 1, n)
Computation can be described following
product = counter * product
counter = counter + 1
(factorial 6)
(fact-iter 1 1 6)
(fact-iter 1 2 6)
(fact-iter 2 3 6)
(fact-iter 6 4 6)
(fact-iter 24 4 6)
(fact-iter 120 6 6)
(fact-iter 720 7 6)
720
Such process is called iterative process
Iterative process can be described by a fixed number of state variables.
When the number of steps of the iterative process is a linear function of the argument then such process is called 'linear iterative process'
If an implementation of procedure generates 'linear iterative process' then we call it tail recursive.
recursive | iterative | |
shape | expands and then shrinks | the same |
state | maintained by interpreter | can be described by fixed number of state variables |
memory complexity | depends on arguments (call stack is used) | constant (if tail call enabled) |
Can we handle this ?
Supported out of the box by
We can describe iterative processes only by resorting to special-purpose looping constructs:
What to do if we deal with recursive function for which call stack is too small ?
def factorial(n):
if n == 1 or n == 0:
return 1
return n * factorial(n - 1)
def factorial(n):
def fact_iter(product, counter, max_count):
if counter > max_count:
return product
return fact_iter(counter * product, counter + 1, max_count)
return fact_iter(1, 1, n)
def factorial(n):
def fact_iter(product, counter, max_count):
while True:
if counter > max_count:
return product
return fact_iter(counter * product, counter + 1, max_count)
return fact_iter(1, 1, n)
def factorial(n):
def fact_iter(product, counter, max_count):
while True:
if counter > max_count:
return product
(product, counter, max_count) = \
(counter * product, counter + 1, max_count)
return fact_iter(1, 1, n)
def factorial(n):
def fact_iter(product, counter, max_count):
while counter <= max_count:
(product, counter, max_count) = \
(counter * product, counter + 1, max_count)
return product
return fact_iter(1, 1, n)
def factorial(n):
product = 1
counter = 1
while counter <= n:
(product, counter) = (counter * product, counter + 1)
return product
A good hint is that problem appears to be built off sub-problems
Problems beginning with
Recursive solutions, by definition, are build off solutions to sub-problems
Many time this means simply to compute f(n) by
Trying to find a pattern and solving for f(0), f(1), f(2)
perm('a') = 'a'
perm('b') = 'b'
perm('c') = 'c'
perm('ab') = 'ab', 'ba'
perm('ac') = 'ac', 'ca'
perm('bc') = 'bc', 'cb'
perm('abc') = 'abc', 'acb', 'bac', 'bca', 'cab', 'cba'
Trying to solve for f(3) using f(2)
perm('a') = 'a'
perm('b') = 'b'
perm('c') = 'c'
perm('ab') = 'a'|perm('b') + 'b'|perm('a')
perm('ac') = 'a'|perm('c') + 'c'|perm('a')
perm('bc') = 'b'|perm('c') + 'c'|perm('b')
perm('abc') = 'a'|perm('bc') + 'b'|perm('ac') + 'c'|perm('ab')
def perm(str):
if len(str) == 1:
return [str]
perms = []
for i in range(0, len(str)):
sub_str = str[:i] + str[(i+1):]
sub_perms = perm(sub_str)
for sub_perm in sub_perms:
perms.append(str[i] + sub_perm)
return perms
perm('abc')
['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
Fibonacci numbers
Fib(0) = 0
Fib(1) = 1
Fib(n) = Fib(n - 1) + Fib(n - 2)
def fib(n):
if n == 0 or n == 1:
return n
return fib(n - 1) + fib(n - 2)
fib(5)
/ \
/ \
/ \
fib(4) \
/ \ \
fib(3) fib(2) \
/ \ / \ \
fib(2) fib(1) fib(1) fib(0) fib(3)
/ \ | | | / \
fib(1) fib(0) 1 1 0 fib(2) fib(1)
| | / \ |
1 0 fib(1) fib(0) 1
| |
1 0
Many redundant computation.
Process shaped like tree
def fib(n):
memo = {}
def fibc(n):
if n in memo:
return memo[n]
if n == 0 or n == 1:
return n
memo[n - 1] = fibc(n - 1)
memo[n - 2] = fibc(n - 2)
return memo[n - 1] + memo[n - 2]
return fibc(n)
def fib(n):
def fib_iter(a, b, count):
if count == 0:
return b
return fib_iter(a + b, a, count -1)
return fib_iter(1, 0, n)
Trampoline is a piece of code that repeatedly calls functions
Here is what the trampoline does
def factorial(n):
def fact_iter(product, counter, max_count):
if counter > max_count:
return product
return fact_iter(counter * product, counter + 1, max_count)
return fact_iter(1, 1, n)
def call(f):
def g(*args, **kwds):
return f, args, kwds
return g
def result(value):
return None, value, None
def with_trampoline(f):
@functools.wraps(f)
def g(*args, **kwds):
h = f
while h is not None:
h, args, kwds = h(*args, **kwds)
return args
return g
def factorial2(n):
def fact(product, counter, max_count):
if counter > max_count:
return result(product)
return call(fact)(counter * product, counter + 1, max_count)
return with_trampoline(fact)(1, 1, n)
factorial(1000)
File "sample.py", line 16, in fact_iter
return fact_iter(counter * product, counter + 1, max_count)
File "sample.py", line 16, in fact_iter
return fact_iter(counter * product, counter + 1, max_count)
File "sample.py", line 14, in fact_iter
if counter > max_count:
RecursionError: maximum recursion depth exceeded in comparison
factorial2(1000)
# 1000! = ...
Thank you -:)