Solving a problem using recursion means sucessively reducing the problem to a simpler form of itself until the solutions are trivial

Factorial `n`

`(n!)`

is the product
of all numbers from `1..n`

`5! = 1·2·3·4·5 = 120`

It can also be defined using recursion
`n! = (n-1)!·n`

`5! = (5-1)!·5 = 120`

`(n-1)!`

is a simpler form of the same problem.
The base case is `0!`

which is by definition `1`

.

```
1 uint32_t factorial(uint32_t n)
2 {
3 if(/*TODO*/) return(1);
4
5 return(factorial(n));
6 }
```

Download the code above and fix
the broken `factorial`

function

```
1 uint32_t factorial(uint32_t n)
2 {
3 if(n==0) return(1);
4
5 return(n*factorial(n-1));
6 }
```

*Observation:*

The code on the previous slide neither specified the base case nor did it reduce the problem towards it

Many problems can be described in a recursive way

```
1 uint32_t arr_max(uint32_t *arr, size_t length)
2 {
3 …
4 uint32_t max_l= arr_max(&arr[0], length_l);
5 uint32_t max_r= arr_max(&arr[length_l], length_r);
6 return(max_l > max_r ? max_l : max_r);
7 }
```

The program above does not work.
Download it, find out what `arr_max`

should do, why it does not work and try to fix it.

`arr_max`

do?`arr_max`

should find the largest number in an array

It splits the array in a right and a left half, calls itself on both halves and returns the largest of the two return values

```
arr_max(1, 2, 3, 4)
=max_2(arr_max(1, 2), arr_max(3, 4))
=max_2(max_2(arr_max(1), arr_max(2)), max_2(arr_max(3), …))
…
```

```
1 uint32_t arr_max(uint32_t *arr, size_t length)
2 {
3 if(length == 1) return(arr[0]);
4 …
5 }
```

The original code was missing a check for the base case

The largest item in an array with only one item is the item itself

```
1 uint32_t tree_max(struct node_t *root)
2 {
3 uint32_t max_val= root->value;
4 …
5 return(max_val);
6 }
```

The `tree_max`

function should return the largest
value in a binary tree using recursion

It does not work. Find the errors and fix them

```
1 if(root->child_l) {
2 uint32_t max_cl= tree_max(root->child_l);
3
4 if(max_cl > max_val) max_val= max_cl;
5 }
```

To make the function recursive `tree_max`

has
to be called on a subset of the previous problem
(the child nodes)

```
1 if(root->child_r) {
2 uint32_t max_cr= tree_max(root->child_r);
3
4 if(max_cr > max_val) max_val= max_cr;
5 }
```

To reach every node in the tree
the left *and* right branch must be taken

```
1 uint32_t tree_max(struct node_t *root)
2 {
3 uint32_t max_val= root->value;
4 …
5 return(max_val);
6 }
```

The code above contains a more difficult to find error

Try to fix it

The following slides are annotations that are intended to help you understand computers a bit better

They are not part of the tutorial or the lecture. You are not required to read or understand them

Please direct any questions regarding them directly to the autor of the slides

They are also oversimplified to make them easier to grasp

When the broken arr_max function runs on the Arduino the Serial monitor displays gibberish

Why is that?

```
0x08FF
-0x08bf main() Variables
…
0x01ff
-0x0100 global Variables
…
0x00ff
-0x0000 "Stuff"
```

Local variables like `arr`

are stored on the
stack

The stack is located at the end of RAM

Global variables, Arduino internal variables, io-Registers and the heap are located at the beginning of the RAM

```
0x08FF
-0x08bf main() Variables
0x08be
-0x089e arr_max() Variables (called from main)
…
0x01ff
-0x0100 global Variables
```

The stack grows for every function call to contain the local variables of the function and an address to jump to when the function is done

```
0x08FF
-0x08bf main() Variables
0x08be
-0x089e arr_max() Variables (called from main)
0x089d
-0x087d arr_max() Variables (called from arr_max)
…
0x01ff
-0x0100 global Variables
```

As there is no base case checking every instance of `arr_max`

will call a new instance of `arr_max`

```
0x08FF
-0x08bf main() Variables
0x08be
-0x089e arr_max() Variables (called from main)
0x089d
-0x087d arr_max() Variables (called from arr_max)
…
0x0170
-0x0150 arr_max() Variables / global Variables
-0x0100 global Variables
```

After a lot of nested `arr_max`

calls the stack will
overflow into the global variables area.
The behavior of the program is now undefined

To prevent stack overflows you should only ever use recursive functions when you know that the calls will not be nested too deeply

Most modern operating systems will prevent the stack from running into the heap and will instead produce an error

In the lecture you got a glimpse at a few "weird" programming languages

One of them is brainfuck. A language designed to be as minimalistic as possible.

A brainfuck program consists only of
the following characters: `><+-.,[]`

All other characters are ignored

Brainfuck operates on an infinite tape like the original turing machine

The characters the program consists of have the following meanings:

```
>/< - move to the next/previous tape position
+/- - increment/decrement the value at the tape position
./, - print/read a character into the tape position
[/] - loop if the value at the tape position is !=0
```

`+++++[>++<-]>[>+++++`

`++>>>>+++>+++++<<<<<`

`<-]>[>+>+>+<<<-]>+>-`

`Informatik ist super`

`->+++>++>[>+>+>+>+<<`

`<<-]>-->->+++++>[<<<`

`<+>>>>-]<<<<<<<<[.>]`

Download the code above, implement the missing operations, disable the debug mode and observe the output of the program