Recurrence Relations · Recursive Definitions

Lesson 5

Nikolai Chukhin · Alexander S. Kulikov

Recursive definitions can describe not only sequences of numbers but also more complex structures. For example, a rooted tree \(T\) can be defined recursively: it is either empty or consists of a root with subtrees \(T_{1}, \dotsc, T_{k}\). In the example below, the root has three children, which are roots of trees with three, one, and four vertices, respectively.

This tree has nine vertices, four of which are leaves. The depth of this tree is four. In general, the number of vertices \(V(T)\), the number of leaves \(L(T)\), and the depth \(D(T)\) of a rooted tree \(T\) (with subtrees \(T_{1}, \dotsc, T_{k}\)) satisfy the following recurrence relations: \[\begin{align*}V(\varnothing)=0,\quad V(T)&=\sum_{i \in [k]}V(T_{i})+1\\ L(\varnothing)=0,\quad L(T)&=\sum_{i \in [k]}L(T_{i})\\ D(\varnothing)=0,\quad D(T)&=\max_{i \in [k]}\{D(T_{i})\}+1\\\end{align*}\] Such recurrence relations are useful when implementing tree algorithms: to apply an operation to a tree (such as computing something or modifying the tree), we perform some actions at the root and then make recursive calls to the subtrees.