2

Possible Duplicate:
Resources for improving your comprehension of recursion?

I am a programmer with 2 years experience, and sometimes think I could solve a specific problem with recursion, but in most cases I fail miserably.

I am asking your advice about resources for learning, refreshing and deepening one's knowledge about recursion, preferably:

  • helping to identify when you could use recursion.
  • practical examples (applied to contemporary programming languages).
  • a reference handbook.
  • source code.
Community
  • 1
Kenny Meyer
  • 139
  • 1
  • 6
  • 22
    See this question: http://programmers.stackexchange.com/questions/158936 – Jesse C. Slicer Jul 31 '12 at 23:38
  • @JesseC.Slicer Took me a bit to get it :P – Dynamic Aug 01 '12 at 00:21
  • 1
    @Jesse: The termination condition in the link is broken or missing. – poke Aug 01 '12 at 00:35
  • recursion *see: recursion* –  Aug 01 '12 at 00:51
  • 1
    I suggest you pick few examples such as factorial calculation, fractals, Fibonacci Numbers, Hanoi Tours, etc. and try to inspect the algorithms one by one carefully and you'll get the concept. Here is a formal lecture if you like: academicearth.org/lectures/thinking-recursively there are other sources of course, but notice that recursion is not always the best method to solve a problem even it is applicable, it is harder to debug and fix. – NoChance Aug 01 '12 at 00:51
  • @poke blast! I was wondering why I got a **StackOverflow** exception! – Jesse C. Slicer Aug 01 '12 at 01:18
  • @JesseC.Slicer: I suppose it had to be done. *Sigh*. I kind of think I've maybe done that once . . . if so, I'm just as bad. –  Aug 01 '12 at 01:51
  • @poke: The termination condition is either "understanding" or "boredom". – Jim G. Aug 01 '12 at 01:51
  • @Jim G.: Ah. Good one. – poke Aug 01 '12 at 03:04

2 Answers2

4

I'm not aware of any recursion-specific books, but it's covered thoroughly in almost any intro to algorithms book.

As far as when you can use recursion, you could use it on practically any algorithm. In some functional programming languages, you must use recursion for things other languages use loops for. If you want to practice recursion, learning a functional language is a good step, and you will find tons of recursion examples in their tutorials.

When it's beneficial to use recursion is another question. Two situations come to mind. The first is when you find yourself using a stack for a data structure. In that situation using recursion automatically gives you a stack, so you don't have to worry about those details. The other situation is when you have a large number of nested loops, or an unknown level of nesting. Recursion makes nesting loops very easy.

The trick to understanding recursion is to not try to hold the entire stack in your head. Focus on just one small part at a time. Think about your current state and trust that the deeper levels are working as advertised.

Karl Bielefeldt
  • 146,727
  • 38
  • 279
  • 479
2

Spotting when to use recursion is actually quite easy - the key concept is noticing that part of the problem is a smaller version of the whole problem. Examples:

  • Functions on lists can be written using recursion if you see that you can achieve the result by doing something with the first element of the list and then calling the function recursively on the rest of the list. Here the "smaller version of the whole problem" is the rest of the list excluding the first element.
  • Functions operating on binary trees can often use recursion by recursively calling the function on the left half of the tree and on the right half of the tree and combining the results in some way. Here the "smaller version of the whole problem" are the left and right sub-trees.
  • Mathematical functions defined recursively (e.g. a function to generate the fibonacci numbers F(n) = F(n-1) + F(n-2) ) often have a simple recursive implementation that mirrors the mathematical definition. Here the "smaller version of the whole problem" are the two previous numbers in the fibonacci sequence.

If you really want to learn about recursion, then picking up a functional language is a good idea - recursion is a natural programming style in functional languages and you'll be steered away from falling back on "imperative" solutions. I'd suggest a Lisp-1 (e.g. Scheme or Clojure) in particular: some of the recursive functions defined on lists are things of beauty.

mikera
  • 20,617
  • 5
  • 75
  • 80