Recursive humor:

:*recursion**see recursion**To understand recursion first you have to understand recursion.*

Recursive abbreviations:

- GNU: GNU's not Unix,
- PHP: PHP Hypertext Preprocessor,
- WINE: WINE Is Not an Emulator,
- TikZ: TikZ is kein Zeichenprogramm.

Examples:

- tower of Hanoi
- Fibonacci numbers
- Pascal triangle (binomial coefficients)

To solve a problem with

- resursion, by reducing a problem to a similar but smaller problems,
- but to avoid recursion, store the previously calculated results in a table.

The Fibonacci numbers are defined with a recursive formula. We will write a function which calculates the Fibonacci numbers. First a non-efficient way, then a more efficient way.

To measure the runtime of the functions we use the `time`

module's `time.time()`

function. This gives the current time in seconds.

The `fibonacci.counter`

is a member of the `fibonacci`

function object.
We use that to count how many times this function way called.

In [1]:

```
import time
def recursive_fib(n):
recursive_fib.counter += 1
if n <= 1:
return n
else:
return recursive_fib(n-1) + recursive_fib(n-2)
recursive_fib.counter = 0
start = time.time()
print recursive_fib(33)
print time.time() - start
print recursive_fib.counter
```

This is terribly slow, the function is called more times than the result itself. You can avoid the lots of function calls just by memorizing the previous results in a list.

In [2]:

```
import time
def dp_fib1(n):
f = [0, 1]
for i in range(n-1):
f.append(f[-2]+f[-1])
return f[-1]
start = time.time()
for i in range(99):
dp_fib1(1000)
print dp_fib1(1000)
print (time.time() - start)/100.0
```

It is even more efficient if you store only the last two values.

In [3]:

```
import time
def dp_fib2(n):
f = [0, 1]
for i in range(n-1):
f = [f[1], f[0] + f[1]]
return f[1]
start = time.time()
for i in range(99):
dp_fib2(1000)
print dp_fib2(1000)
print (time.time() - start)/100.0
```

Exercise: given three rods with disks on them. The disks have an increasing radius and the rules are:

- you can move only one disk at a time
- bigger disk cannot be on top of a smaller disk

Move a stack of disks from one rod to an other!

Recursive solution: if you want to move $n$ disks from rod $A$ to rod $B$ then

- first you have to move the top $n-1$ disks from rod $A$ to rod $C$
- then move the bottom disk to rod $B$
- finally move the $n-1$ disks from rod $C$ to their final position to rod $B$

This solution is easy to programming but not that efficient.

In [4]:

```
def hanoi(n, source, destination, auxiliary):
if n>0:
hanoi(n-1, source, auxiliary, destination)
print "move disk no.{0} from {1} to {2}".format(n, source, destination)
hanoi(n-1, auxiliary, destination, source)
```

In [5]:

```
hanoi(3,"A","B","C")
```

The non-recursive solution is more efficient but harder to write the code.

Let's say that you have a given type of bank notes: $\$1, \$2, \$5, \$10$ and so on.

You want to pay a given amount of money with the least possible number of banknotes. For example paying $\$10$ with 10 times a one dollar note is not optimal. But paying $\$8$ is optimal with $\$1+\$2+\$5$

Suppose that you have unlimited number of banknotes, find the optimal number of banknotes to pay a given amount of money!

The ** greedy algorithm** works in this case:

- Find the biggest note which covers not more than the target amount
- Subtract that from the target amount
- Continue until the target is $\$0$

Although, this failes of the banknotes are different: for example if you have $\$1, \$5, \$8, \$10, \$20$ then it is easier to pay in $\$8+\$8+\$8$ notes than $\$20+\$1+\$1+\$1+\$1$ (which is solution of the greedy algorithm).

Note that the possible coins are stored in a global variable.

In [6]:

```
import time
def recursive_exchange(target):
recursive_exchange.counter += 1
n_coins_min = float('inf')
if target in coins:
return 1
else:
for coin in coins:
if coin > target:
break
number_of_coins = 1 + recursive_exchange(target - coin)
if number_of_coins < n_coins_min:
n_coins_min = number_of_coins
return number_of_coins
recursive_exchange.counter = 0
coins = [1,2,5,10,20]
start = time.time()
print recursive_exchange(34)
print time.time() - start
print recursive_exchange.counter
```

In [7]:

```
recursive_exchange.counter = 0
ermek = [1,8,5,10,20]
start = time.time()
print recursive_exchange(24)
print time.time() - start
print recursive_exchange.counter
```

It works OK but there is a faster solution.

Not only calculate the optimal coins for a given target, but all smaller amounts also. We will store the optimal coin numbers from 0 up to the target value. In this way you don't have to calculate the same thing twice.

Let's go through the possible coins and try to pay the amount with that coin.

```
optimal(target) = coin + optimal(target-coin)
```

And look for the optimum by selecting the smallest over all coins.

In formula for example with coins $\$1, \$2, \$5$ and the total amount of $\$24$: $$\texttt{optimal[24]}=1+\min\left\{\begin{array}{l}\texttt{optimal[24-1]}\\\texttt{optimal[24-5]}\\\texttt{optimal[24-10]}\end{array}\right\}$$

In [8]:

```
def dynamic_exchange(target):
global table
table = [0]*(target+1)
for t in range(1, target+1):
min_coins = float('inf')
for coin in coins:
if coin > t:
break
if table[t-coin] + 1 < min_coins:
min_coins = table[t-coin] + 1
table[t] = min_coins
return table[target]
```

In [9]:

```
coins = [1,2,5,10]
start = time.time()
print dynamic_exchange(24)
print time.time() - start
```

In [10]:

```
print table
```

In [11]:

```
coins = [1,2,5,8,10]
start = time.time()
print dynamic_exchange(24)
print time.time() - start
```

In [12]:

```
print table
```

In [13]:

```
coins = [5,10,20,50]
start = time.time()
print dynamic_exchange(84)
print time.time() - start
```

In [14]:

```
print table
```

Exercise: How many ways can you decompose an integer into sum of positive integers (order matters)? For example you can write $3 = 1+1+1 = 1+2 = 2+1$, there are four ways to decompose. We will solve this with recursion and with dynamic programming.

In [15]:

```
def sums(n):
if n == 0:
return [[]]
if n == 1:
return [[1]]
else:
sumlist = []
for i in range(1,n+1):
L = [i]
for l in sums(n-i):
sumlist.append(L + l)
return sumlist
for s in sums(4):
print " + ".join(str(x) for x in s)
```

In [16]:

```
def sums_d(n):
global table
table = [[[]], [[1]]]
if n == 0 or n == 1:
return table[n]
for i in range(2, n+1):
sumlist = [[i]]
for j in range(1, i):
for l in table[i - j]:
sumlist.append([j] + l)
table.append(sumlist)
return table[n]
```

In [17]:

```
for s in sums_d(4):
print " + ".join(str(x) for x in s)
```

In [18]:

```
print table
```

In [19]:

```
print "\"Hello\"\nbackslash: \\not a new line"
```

For a backslash character the parser goes into a listening state which means that the next character is treated differently.

Let's say that you read the string character-by-character and have a state variable `s=0`

.

- If you encounter a backslash and
`s=0`

: set`s=1`

- If you encounter
`n t "`

or`'`

and`s=1`

then- you have a special character
- if you encounter a backslash when
`s=1`

then it is still a special character - in these cases reset
`s=0`

- if you encounter any other character then just set
`s=0`

In [20]:

```
sample = r"\"Hello\"\nbackslash: \\not a new line"
s = 0
for i in sample:
if i == "\\":
if s == 0:
s = 1
else:
print "\\"
s = 0
elif i in 'nt"\'':
if s == 1:
s = 0
print i
else:
s = 0
```

Count how many parentheis are in a formula.
Let's start with `s=0`

and increase `s`

whenever you find a `"("`

and decrease it when you find a `")"`

.

If the counter becomes negative then some of the parenthesis are wrong. Or if the counter is not 0 at the end of the string then the parenthesis are wrong, too.