Recursion Resources + Help

[Aaron Vienneau]

I get the feeling that recursion is a lost art in programming.

Most everything that can be done recursively can be done iteratively -- However, it's arguable that SOME tasks are much easier and more intuitive to program recursively.

I get the feeling that because recursion is a bit more abstract than iteration, people just kinda skim chapters on recursion. However, I'm really interested in it! Although...I have to admit, I'm one that struggles with it. ( I too skimmed over it, and now want to go back and fill in some missing pieces in my programming knowledge).

Does anyone have good resources on an explaination of recursion that is chalked full of examples and exercises? I almost feel like I'd need an entire book dedicated to that one subject to get a grasp on it.

[Veltas]

How is recursion a "lost art"? It's just a technique that people use sometimes and nothing too special. Sometimes you get some elegant code with it but it's a trade-off as it's slower and can cause stack-overflows compared to an iterative alternative that wouldn't.

1! =1, 0! = 1
n! = n * (n - 1)!

So:

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

Which is a slower and less stable version of:

int factorial(int n)
{
  int result = 1;
  while (n >= 1) {
    result *= n;
    --n;
  }
  return result;
}

I imagine your book probably covers as much detail if not less than the wikipedia article on recursion.
https://en.wikipedia.org/wiki/Recursion_(computer_science)
Read through that if you want to gussy-up.

There's no special trick to recursion, if you feel like there's more to it then you're right, but it's mainly specific to different situations so you just have to think logically about it.

On the subject of recursion, as it lends itself towards it (although is not bound by it), I could mention memoization. This is a neat technique that basically involves remembering a result in a sub-problem (i.e. storing the result of a top-level recursion step so that it is only fully-called once and other times it just looks up the result). But this could be used in any situation where you split the issue up into sub-problems.

Algorithms that split up an issue into sub-problems come of two main forms: divide and conquer, and dynamic programming.

In dynamic programming one splits a problem into sub-problems that don't partition the problem but are all needed to solve the overall problem (i.e. the sub-problems overlap, or are repeated). If the sub-problems are repeated as a result one can use memoization to cut down on the processing needed to solve the problem, as it will solve a sub-problem only once and then if the answer is needed again it can look it up.

In divide and conquer one partitions the input into smaller groups in order to solve smaller problems separately to get the answer. So divide and conquer can be programmed with recursion (but not memoization). An interesting divide-and-conquer algorithm that can be programmed recursively is Quick Sort.

Further reading:
https://en.wikipedia.org/wiki/Memoization
https://en.wikipedia.org/wiki/Dynamic_programming
https://en.wikipedia.org/wiki/Divide_and_conquer_algorithm
https://en.wikipedia.org/wiki/Quick_sort