Extensive Recursion Tutorial

Question

Some problems requiring recursion always put me in a fix. I can’t always find a recursive algorithm, but I know that there is a recursive solution to the problem.

I believe that problems like factorial and fibonacci are easily implemented using a recursive approach. But when I have to deal with more complex problems, such as creating the number section http://en.wikipedia.org/wiki/Partition_%28number_theory%29 , I know that there is a possible recursive approach, but I got stuck right there. I cannot develop a recursive algorithm. Suppose I want to print all the combinations of a string, or if I want to use the Change Coins command with recursion, I cannot develop a recursive approach.

Is there any specific way to think in order to come up with a recursive approach? Is there an extensive recursive algorithm that will help me solve more complex problems?

Answer 1

Browse the Structure and interpretation of a computer program book , which is highly recommended here for and freely available online. It uses the programming language Schemes to teach fundamental programming concepts. Since Scheme is a functional programming language, recursion is widely used everywhere - not only where you will use it even in imperative programming languages ​​such as C or PHP, but also where you usually use a loop. The examples and problems in the book represent recursion in its natural habitat, if you will, rather than through complicated scripting inventions.