Tree - (Recursion|Induction) Algorithm

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

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.

Tree definiton

The tree can be:

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)
     }

Documentation / Reference


Powered by ComboStrap