## Recursion

A quick introduction

L2L Warszawa 2017

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)
``````
Computation can be described following
``````
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

• 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

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! = ...
``````

Thank you -:)