Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.
share|improve this question

marked as duplicate by Jarrod Roberson, Mark Trapp, gnat, Walter, psr Aug 1 '12 at 17:24

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

19  
See this question: 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 1 '12 at 0:21
1  
@Jesse: The termination condition in the link is broken or missing. –  poke Aug 1 '12 at 0:35
    
recursion see: recursion –  Jarrod Roberson Aug 1 '12 at 0: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. –  Emmad Kareem Aug 1 '12 at 0:51
show 4 more comments

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
This was the kind of answer I was looking for. Thank you! I would you up more if I could. –  Kenny Meyer Aug 1 '12 at 22:03
add comment

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.

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.