# Tree - (Recursion|Induction) Algorithm

### Table of Contents

## 1 - About

A recursive algorithms invoke themselves as a subroutine with a smaller input.

The idea of the recursion tree method is to write out all of the work done by the recursive algorithm in a tree structure, with the children of a given node corresponding to the recursive calls made by that node.

See Mathematics - Logarithm Function (log)

The relationship between the elements is called a Recurrence relation

## 2 - Articles Related

## 3 - Base case

Recursive algorithms need a base case so they don't keep calling themselves until the rest of time. When the input's sufficient (small), you stop the recursion and you just return some trivial answer.

## 4 - Tree definiton

The tree can be:

- a predefined structure
- or a function

### 4.1 - Tree Function

Example: defining a sequence of number by recursion Ref. A tree function is known as a recurrence relation and is a function that expresses each element of a sequence as a function of the preceding ones.

```
seq = ();
def recurenceRelation(x):
x = seq.add(x)
if (x <10){
recurenceRelation(x+1)
}
```