What are recursion trees?

Question

While reading more on merge sort I came across recursion trees. What are recursion trees? Do they help in solving recursive problems? What do we achieve by drawing a recursion tree? Google did not help me.

Answer 1

A recursion tree can demonstrate how useful recursion might be in solving your problem, and could also help reveal worse/best case scenarios. For instance, if your binary search algorithm's recursion tree is always taking the right most path, you're probably in a worse-case scenario (because your program isn't branching, why even use a tree to represent it?). Drawing a tree of the recursive operation of your algorithm over a set of inputs can also spark ideas in your mind as to how to change your recursive program to iterative which may or may not save a lot of memory/time.

Alternatively it could make your recursive program look really good because you might find it fills out just about all the leaves before moving on to the next layer and sets you up to operate very quickly on the tree. A good example of this is a red-black binary search tree, but that's a bit more difficult to map out in a recursive way than a merge sort.