O'Reilly logo

Introduction to Recursive Programming by Manuel Rubio-Sanchez

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

3.3.1 Expansion method

The expansion methodExpansion method, also known as the “iterationIteration!method|see expansion method” or “backward substitutionBackward substitution|see expansion method” 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. ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required