Mastering Recursive Programming [closed]

Question 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

Math operations: Exponentiation and every mathematical operation you can think of.
String handling: Palindrome is a very good exercise. Finding words in a grid is also useful.
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.
Combinatorial problems: Very important, combinations, permutations, etc.
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!

Question 2

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 !

Question 3

recursion is hard because it is a different way of thinking, one that we were never introduced to when we were younger.

from what you are saying you already have the concept all you really need is just to practice it more. a functional language would definitely help; you will be forced to think about your problems recursively and before you know it recursion will seem very natural

there are tons of exercises you can do related to recursion, keep in mind that anything done with a loop can be done recursively as well.

see this answer for a great details about references and exercise probelms

Question 4

Studying a functional language would certainly help you think in recursion. I would recommend either Haskell or Lisp (or Clojure). The nice thing is, you don't need to get to the "hard bits" of either of these languages before getting to the recursion. To learn about recursion, you don't have to learn enough of either of these languages to do "real" programming.

Haskell's pattern-matching syntax means that base cases are easy to see. In Haskell, Factorial looks like this:

factorial 0 = 1
factorial n = n * factorial (n - 1)

... which is exactly equivalent to a procedural language's:

int factorial(n) {
    if(n==0) {
         return 1;
    } else {
         return n * factorial(n-1)
    }
}

... but with less syntax to obscure the concept.

For completeness, here is the same algorithm in Lisp:

(defun factorial (n)
   (if (== n 0)
       1
       (* n (factorial (- n 1)))))

Which you should be able to see is equivalent, although at first all the parentheses tend to obscure people's view of what's going on. Still, a Lisp book will cover a lot of recursive techniques.

In addition, any book on a functional language will give you lots of examples of recursion. You'll start with algorithms that work with lists:

 addone [] = []
 addone (head:tail) = head + 1 : addone tail

.. which uses a very common pattern with one recursive call per function. (Actually a pattern so common that almost all languages abstract it into a library function called map)

Then you'll move on to functions that traverse trees, by making one recursive call for each branch from a node.

More generally, think of problems like this:

"Can I solve a small part of this problem, and leave myself with the same problem, only smaller?".

... or ...

"Would this problem be easy to solve, if only the rest of it was already solved?".

So, for example, factorial(n) is simple to work out if you know factorial(n-1), which suggests a recursive solution.

It turns out that lots of problems can be thought of that way:

"Sorting a list of 1000 items seems hard, but if I pick a random number, sort all the numbers smaller than that, then sort all the numbers larger than that, I'm done." (Eventually comes down to sorting lists of length 1)

...

"Calculating the shortest path to a node is hard, but if I could just know the distance to there from each of my adjacent nodes, it would be easy."

...

"Visiting every file in this directory tree is hard, but I can look at the files in the base directory, and threat subdirectories the same way."

Likewise the Tower of Hanoi. The solution is easy if you state it like this:

 To move a stack from a to c:
  If the stack is of size 1
      just move it.
  otherwise
      Move the stack minus its largest ring, to b (n-1 problem)
      Move the largest ring to c (easy)
      Move the stack on b to c (n-1 problem)

We've made the problem look easy by sketching over two apparently difficult steps. But those steps are just the same problem again, but "one smaller".

You may find it useful to manually step through a recursive algorithm using pieces of paper to represent the call stack, as described in this answer: Understanding stack unwinding in recursion (tree traversal)

After you've got more comfortable with recursion, circle back and think about whether it's the right solution for a particular case. Although factorial() is a good way to demonstrate the concept of recursion, in most languages an iterative solution is more efficient. Find out about tail recursion optimisation, which languages feature it, and why.

Question 5

Recursion is a convenient way to implement the Divide & Conquer paradigm: when you need to solve a given problem, a powerful approach is to break it into problems of the same nature, but with a smaller size. By repeating this process, you will end up working on problems so small that they can be solved easily by another method.

The question you have to ask yourself is "can I solve this problem by solving parts of it ?". When the answer is positive, you apply this well-known scheme:

split the problem into subproblems recursively, until the size is small,
solve the subproblems by a direct method,
merge the solutions in the inverse order.

Note that the splitting can be made in two parts or more, and these can be balanced or not.

For example: can I sort an array of numbers by performing partial sorts ?

Answer 1: yes, if I leave the last element out and sort the rest, I can sort the whole array by inserting the last element at the right place. This is insertion sort.

Answer 2: yes, if I find the largest element and move it to the end, I can sort the whole array by sorting the remaining elements. This is selection sort.

Answer 3: yes, if I sort two halves of the array, I can sort the whole array by merging the two sequences, using an auxiliary array for movements. This is merge sort.

Answer 4: yes, if I partition the array using a pivot, I can sort the whole array by sorting the two parts. This is quick sort.

In all these cases, you solve the problem by solving subproblems of the same nature and adding some glue.

Question 6

For complex problems, I suggest doing the problem for small problem sizes and seeing what kinds of patterns you find. For example, in Towers of Hanoi, start with a problem size of one, then two, then three, etc. At some point, you'll probably start to see a pattern, and you'll realize that some of what you are having to do is just like what you had to do on the smaller sized problems, or that it is similar enough that you can use the same technique as before but with some variation.

I just went through the Towers of Hanoi problem myself and studied my own thinking. I started with a problem of size one:

   We have one disk on peg A.
   *** Move it to peg C.
   Done!

Now for two.

   We have two disks on peg A.
   I need to use peg B to get the first disk out of the way.
   *** Move from peg A to peg B
   Now I can do the rest
   *** Move from peg A to peg C
   *** Move from peg B to peg C
   Done!

Now for three.

Things start to get a little more interesting. The solution isn't as obvious. However, I've figured out how to move two disks from one peg to another, so if I could move two disks from peg A to peg B, then move one disk from peg A to peg C, and then two disks from peg B to peg C, I'd be done! My logic for the case of two disks will work, except that the pegs are different. If we put the logic into a function, and make parameters for the pegs, then we can re-use the logic.

def move2(from_peg,to_peg,other_peg):
   # We have two disks on from_peg
   # We need to use other_peg to get the first disk out of the way
   print 'Move from peg '+from_peg+' to peg '+other_peg
   # Now I can do the rest
   print 'Move from peg '+from_peg+' to peg '+to_peg
   print 'Move from peg '+other_peg+' to peg '+to_peg

The logic is then:

       move2('A','B','C')
       print 'Move from peg A to peg C'
       move2('B','C','A')

I can make this simpler by having a move1 function also:

def move1(from_peg,to_peg):
    print 'Move from '+from_peg+' to '+to_peg

Now my move2 function can be

def move2(from_peg,to_peg,other_peg):
   # We have two disks on from_peg
   # We need to use other_peg to get the first disk out of the way
   move1(from_peg,other_peg,to_peg)
   # Now I can do the rest
   move1(from_peg,to_peg)
   move1(other_peg,to_peg)

Ok, what about four?

Seems like I can apply the same logic. I need to get three disks from peg A to peg B, then one from A to C, then three from B to C. I've solved moving three already, but with the wrong pegs, so I'll generalize it:

def move3(from_peg,to_peg,other_peg):
   move2(from_peg,other_peg,to_peg)
   move1(from_peg,to_peg)
   move2(other_peg,to_peg,from_peg)

Cool! And wait, move3 and move2 are pretty similar now, and that makes sense. For any sized problem we can move all but one of the disks to peg B, then move one disk from A to C, then move all the disks on peg B to peg C. So our move function can just take the number of disks as a parameter:

def move(n,from_peg,to_peg,other_peg):
    move(n-1,from_peg,other_peg,to_peg)
    move1(from_peg,to_peg)
    move(n-1,other_peg,to_peg,from_peg)

This looks really close, but it doesn't work in the case where n==1 because we end up calling move(0,...). So we need to handle that:

def move(n,from_peg,to_peg,other_peg):
    if n==1:
        move1(from_peg,to_peg)
    else:
        move(n-1,from_peg,other_peg,to_peg)
        move1(from_peg,to_peg)
        move(n-1,other_peg,to_peg,from_peg)

Excellent! What about a problem size of five? We just call move(5,'A','C','B'). Looks like any problem size is the same thing, so our main function is just:

def towers(n):
    move(n,'A','C','B')

and we're done!