Recursion
A quick introduction
L2L Warszawa 2017
About me
Sławomir Śledź
Senior Java Developer
The Talk
-
Recursion in theory
- recursive procedure/function
- recursive process
- recursion call to iteration transformation
-
Practical approach to solve recursive problems
- how to recognize
- how to approach
- some examples
-
Backup slides
- tree recursion
- trampoline
Recursion
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
Recursive procedure
Informal definition says that recursive procedure is a procedure which calls itself.
Can be defined by two properties:
- a simple base case - termination scenario (does not use recursion)
- a set of rules that reduce all other cases toward the base case
Procedure vs Process
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)
Example of recursive procedure
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)
Linear recursive process
(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
Observation
- expansion proceeds as if the process is building a chain of deferred operations
- contraction occurs when operations are actually performed
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'
Factorial v2
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)
product = counter * product
counter = counter + 1
Linear iterative process
(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
Observation
- shape of the process does not expand
-
for each step, in order to fully describe the state we need only those variables:
- product
- counter
- max_count
- last action of the procedure does not need to build up a new call frame
Such process is called iterative process
Observation
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 vs Iterative - Summary
| 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) |
Price of recursion
- Deferred long call chain can introduce 'Stack overflow'
- Consumes more memory
Can we handle this ?
Tail call optimization
Supported out of the box by
- Common Lisp, Scheme, Racket (Lisp dialects)
- Scala
- Kotlin
- Lua
- Tcl
- Perl (using special construct)
- Elixir (runs on Erlang vm)
- JavaScript - ECMAScript 6.0
What about other common languages
We can describe iterative processes only by resorting to special-purpose looping constructs:
- do
- repeat
- until
- for
- while
How to approach heavy recursive functions
What to do if we deal with recursive function for which call stack is too small ?
- convert recursive call into tail recursive (if language supports tail call optimization)
- convert recursive call into iteration
- try to manage call stack by your own (very inefficient)
How to convert recursive calls into iteration in 4 steps
- try to convert all recursive calls into tail calls (If you can't try another method)
- introduce one-shot loop around the function body
- convert tail calls into assignments statements
- make cleanup
Convert all recursive calls into tail calls
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)
Introduce one-shot loop around the function body
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)
Convert tail calls into assignments statements
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)
Cleanup
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)
Cleanup
def factorial(n):
product = 1
counter = 1
while counter <= n:
(product, counter) = (counter * product, counter + 1)
return product
Practical approach to solve recursive problems
- How to recognize
- How to approach
- Some examples
How to recognize that we deal with recursion
A good hint is that problem appears to be built off sub-problems
Problems beginning with
- compute the nth... (generate nth Fibonacci number)
- compute/print/return all... (return all subsets of a set)
- list the first n...
How to approach in order to solve the problem
Recursive solutions, by definition, are build off solutions to sub-problems
Many time this means simply to compute f(n) by
- adding something
- removing something
- changing the solution for f(n-1)
- or doing something more complicated :)
Some guidelines
- think about what the sub-problem is, how many sub-problems does f(n) depend on (in a fibonacci - 2, linked list - 1)
- solve for a 'base case', so if you need to compute for f(n), first compute it for f(0) or f(1) - this is a usually hard-coded value
- solve for f(2)
- understand how to solve for f(3) using f(2) - understand how to translate a solution for sub-problems into real solution
- generalize for f(n)
Examples
- Compute all permutation of a string (on slides)
- Compute all permutations of a string in Java
- Return all subset of a set in Java
Compute all permutation of a string
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'
Compute all permutation of a string
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')
Compute all permutation of a string
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']
Backup slides
- tree recursion
- trampoline
Tree recursion
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)
Tree recursion
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
Observation
Many redundant computation.
Process shaped like tree
How to approach ?
- Try to rewrite to have iterative process
- Dynamic programming
- problem must have an optimal substructure
- implementation - memoization
Dynamic programming
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)
Iterative version
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)
Tail call optimization through trampoline
Trampoline is a piece of code that repeatedly calls functions
Here is what the trampoline does
- call function f
- if function f wants to make a recursive call to itself, it returns the instruction - call(f)(*args, **kwds)
- trampoline interprets the instruction, and calls f back
- this process repeats until f wants to return a final result z, then it returns instruction result(z)
- trampoline interprets instruction result(z) by returning z to its caller
Example of transformation
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)
Running code
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! = ...
Resources
Thank you -:)