Mastering Recursive Programming

Question

I am having trouble in thinking/solving the problem in terms of recursion. I really appreciate the concept and I can understand them like creating base case, exit case & the recursive calls etc. I can solve simple problems like writing factorial or summation of integers in an array. That's where my thinking stops. I couldn’t really apply the concepts or come up with solutions when problem gets complicated. For instance, tower of Hanoi, though I can understand the problem and solution, I, on my own can't up with a solution. It applies to other algorithms like quick sort/binary tree traversal as well. So my question is

1. What is the best way to master it?
2. Can anyone suggest a list of problems or questions, which I can use as an exercise to practice it?
3. Will learning functional language help me with my understanding?

Please advice.

Answer 1

Recursion is just a way of thinking, just as iterative is. When we were kids at school, we weren't taught to think recursively and there lies the real problem. You need to incorporate that way of thinking into your arsenal, once you do it, it'll stay there forever.

Best way to master:

I found useful to always figure out the base cases first, maybe at first they aren't the most simple ones, but once you start building the recursion on top of that base case you'll realize you can simplify it. The importance of identifying the base case is that first, you focus on what needs to be solved at its simplest form (the simpler cases) and this somehow draws a road map for the future algorithm, second, you make sure the algorithm stops. Maybe doesn't return the expected result, but at least stops, which is always encouraging.

Also, it always help figuring out how a small instance of a problem will help you finding the solution of a bigger instance of the problem. This is for example, how can you build the solution for input n having already the solution of input n-1.

Solve every problem you can think of recursively. Yes, Hanoi Towers ain't a very good example, its recursive solutions is a very clever solution. Try easier problems, almost elemental problems.

List of problems

1. Math operations: Exponentiation and every mathematical operation you can think of.
2. String handling: Palindrome is a very good exercise. Finding words in a grid is also useful.
3. Learn about tree data structures: This in particular is IMO the best training. Trees are recursive data structures. Learn about their traversals (inorder, postorder, preorder, calculate its height, its diameter, etc). Almost every operation on a tree-like data structure is a great exercise.
4. Combinatorial problems: Very important, combinations, permutations, etc.
5. Path finding: Lee's algorithm, Maze algorithms etc.

But most importantly, begin with simple problems. Almost every problem have a recursive solution. Math problems are great to get a grasp of it. Every time you see a for loop or a while loop, turn that algorithm into recursion.

Programming language

Functional programming relies heavily on recursion. I don't think that should help much since they are inherently recursive and can be cumbersome for users who don't understand recursion very much yet.

Use a simple programming language, the one you're most familiar with, preferably one that doesn't busy your mind much with memory annoyances and pointers. Python is a very good start in my opinion. Is very simple, doesn't bother you with typing or complicated data structures. As long as the language helps you stay focused only on recursion, it will be better.

One last advice, if you can't find a solution to a problem, search for it on the internet or call for help, understand what it does completely and move on to the other. Don't let them bypass you, because what you're trying to do is incorporate that way of thinking to your head.

To master recursion, you need first master recursion :)

Hope this helps!