ABSTRACT
Tail recursion, also known as "final" recursion, is a form of linear recursion in the sense that the recursive cases only invoke the method once. However, in tail recursion a recursive call is the last action performed by the method. Most programming languages support short-circuit evaluation. However, it can be forced by considering an additional base case, which leads to a tail-recursive algorithm. It is important to understand that although the chosen decomposition divides the input by a constant, the size of the problem is only reduced by a unit. Binary tree search is a data structure used for storing data items, each of which is associated with a certain key, similarly to the entries in a Python dictionary. A simple idea consists of scanning the entire input list in order to build: a new list that contains elements that are smaller than or equal to the pivot, and another list formed by the elements that are greater than pivot.
