Introduction to Recursive Programming

3.3.1 Expansion method

The expansion method, also known as the “iteration” or “backward substitution” method, can be used primarily to solve recurrence relations whose recursive case contains one reference to the recursive function (in some cases it can be applied to recurrences where the recursive function appears several times in the recursive definitions). The idea consists of simplifying the recurrence relation progressively step by step, until noticing a general pattern at some i-th stage. Subsequently, the function can take concrete values by considering that the base case is reached at that i-th step. The following examples illustrate the procedure. Finally, Section 10.2.1 illustrates a related visual approach called the “tree method.” ...