Mastering Recursive Programming [closed]

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!

My piece of advice: trust that the recursive function "does the job", i.e. fulfills its specification. And knowing that, you can build a function that solves a larger problem while still fulfilling the specification.

How do you solve the Hanoi towers problem ? Assume there is a function Hanoi(N) able to move a pile of N disks without infringing the rules. Using this function, you easily implement Hanoi'(N+1): perform Hanoi(N), move the next disk and perform Hanoi(N) again.

If Hanoi(N) works, then Hanoi'(N+1) works as well, without infringing the rules. To complete the argument, you must make sure that the recursive calls do terminate. In this case, if you can solve the Hanoi(1) non recursively (which is trivial), you are done.

Using this approach, you don't have to worry about how things will actually occur, you are guaranteed that it works. (Provided you move to smaller and smaller instances of the problem.)

Another example: recursive traversal of a binary tree. Assume the function Visit(root) does the job. Then, if left -> Visit(left); if right -> Visit(right); print root will do the job ! Because the first call will print the left subtree (don't worry how) and the second the right subtree (don't worry how), and the root will be printed too.

In the latter case, termination is guaranteed by the fact that you process smaller and smaller subtrees, down to leaves.

Other example: Quicksort. Assume you have a function that sorts an array in-place, let Quicksort. You will use it as follows: move small elements before large elements, in-place, by comparing them to a well-chosen "pivot" value (actually, any value from the array can do). Then sort the small elements by means of the Quicksort function, and the large elements the same way, and you are done ! No need to wonder the exact sequence of partitions that will take place. Termination is ensured if you avoid void subarrays.

Last example, Pascal's Triangle. You know that an element is the sum of the two above it, with 1's on sides. So with closed eyes, C(K, N)= 1 if K=0 or K=N, else C(K, N) = C(K-1, N-1) + C(K, N-1). That's it !