13

I know what recursion is (when a patten reoccurs within itself, typically a function that calls itself on one of its lines, after a breakout conditional... right?), and I can understand recursive functions if I study them closely. My problem is, when I see new examples, I'm always initially confused. If I see a loop, or a mapping, zipping, nesting, polymorphic calling, and so on, I know what's going just by looking at it. When I see recursive code, my thought process is usually 'wtf is this?' followed by 'oh it's recursive' followed by 'I guess it must work, if they say it does.'

So do you have any tips/plans/resources for building up skills in this area? Recursion is kind of a weird concept so I'm thinking the way to tackle it may be equally weird and inobvious.

Anna S
  • 5
  • 3
Andrew M
  • 1,121
  • 9
  • 19
  • 28
    To understand recursion, you must first understand recursion. – Andreas Johansson Mar 11 '11 at 22:10
  • 1
    'The Cat in Hat Comes Back' by Dr. Seuss, this may not be entirely useful, but the recursive call on the cat does get rid of that pesky stain. :-) It also has the benefit of being a very quick read! – DKnight Mar 11 '11 at 22:15
  • 2
    Practice, practice, practice. – David Thornley Mar 11 '11 at 22:15
  • 20
    Already answered in this question: http://programmers.stackexchange.com/questions/57243/resources-for-improving-your-comprehension-of-recursion – Graham Borland Mar 11 '11 at 22:17
  • 3
    @Graham Borland: That's an example of infinite recursion. In most programs, missing the base case usually results in a stack overflow or out-of-memory error. For website users, it might just result in confusion. ;) – FrustratedWithFormsDesigner Mar 11 '11 at 22:23
  • 1
    http://www.amazon.com/Calculus-Semantics-Studies-Foundations-Mathematics/dp/0444875085 – SK-logic Mar 12 '11 at 09:54
  • possible duplicate of [In plain English, what is recursion?](http://programmers.stackexchange.com/questions/25052/in-plain-english-what-is-recursion) – haylem Mar 03 '12 at 12:15

9 Answers9

10

Start with something simple and trace it out with pencil and paper. Seriosuly. A good place to start is tree-traversal algorithms, since they are much more easily handled using recursion than regular iteration. It doesn't have to be a complicated example, but something that is simple and you can work with.

Yes, it's weird and sometimes counter-intuitive, but once it clicks, once you say "Eureka!" you'll wonder how you didn't understand it before! ;) I suggested trees because they are (IMO) the easiest structure to understand in recursion, and they are easy to work with using a pencil and paper. ;)

FrustratedWithFormsDesigner
  • 46,105
  • 7
  • 126
  • 176
  • 1
    +1 this is the way I grokked it. e.g. if you're using OO make some classes with a parent child relationship and then try and make a function/method that checks if an object has a specific ancestor. – Alb Mar 12 '11 at 01:46
5

I strongly recommend Scheme, using the book The Little Lisper. Once you're done with it, you will understand recursion, deep down. Almost guaranteed.

jcomeau_ictx
  • 355
  • 2
  • 5
4

I definitely suggest SICP. Also, you should check out the authors' introductory course videos here; they're incredibly mind-opening.

Another road, not so strictly related to programming, is reading Gödel, Escher, Bach: an Eternal Golden Braid by Hofstadter. Once you get trough it, recursion will look as natural as arithmetics. Also, you'll be convinced that P=nP and you're going to want to build thinking machines - but it's a side-effect that's so small when compared to the benefits.

cbrandolino
  • 1,999
  • 1
  • 18
  • 21
  • _GEB_ is worth reading anyway; even if some of the things he talks about are a little bit dated (some progress on fundamental CS research has been made in the past 40 years) the basic understanding isn't. – Donal Fellows Apr 16 '13 at 07:13
2

Essentially it just comes down to practice... Take general problems (sorting, searching, math problems, etc.) and see if you can see a way in which those problems can be solved if you apply a single function several times.

For example quick sort operates in that it moves element in a list into two halves and then applies itself again to each of those halves. When the initial sorting occurs its not worried about getting the two halves sorted at that point. Rather its taking the pivot element and putting all elements smaller than that element on one side and all elements larger than or equal to on the other side. Does this make sense how it can recursively call itself at that point to sort the two new smaller lists? They're lists too. Just smaller. But they still need to be sorted.

The power behind recursion is the divide and conquer notion. Break a problem repeatedly into smaller problems which are identical in nature but just smaller. If you do that enough eventually you get to a point where the only remaining piece is already solved then you just work your way back out of the loop and the problem is solved. Study those examples you mentioned until you understand them. It may take a while but eventually it will get easier. Then try to take other problems and make a recursive function to solve them! Good luck!

EDIT: I must also add that a key element to recursion is the guaranteed ability of the function to be able to stop. This means the break down of the original problem must continuously get smaller and eventually there needs to be a guaranteed stopping point (a point at which the new sub problem is either solvable or already solved).

Kenneth
  • 2,703
  • 2
  • 21
  • 30
  • Yeah I think I've seen a quick sort explanation before, I can envision how it works from your reminder above. How expressive/flexible is recursion - can most problems be coerced into a recursive approach (even if it's not optimal)? I've seen people answer coding puzzles on the net that most people were tackling procedurally, as if they could use recursion whenever they wanted just for the hell of it. I also read once, I think, that some languages depend or recursion to replace the loop construct. And you mention the guaranteed stopping point. I feel like one of those things may be the key. – Andrew M Mar 11 '11 at 22:38
  • A good simple starting problem for you to create on your own would be to write a recursive program that finds the factorial of a number. – Kenneth Mar 11 '11 at 22:40
  • Any looping structure can be put into a recursive structure. Any recursive structure can be put into a looping structure... more or less. It takes time and practice to be able to learn when and when not to use recursion because you have to remember that when you use recursion there's a LOT of overhead in terms of resources used at the hardware level. – Kenneth Mar 11 '11 at 22:42
  • For example I could see it being feasible to create a looping structure that performs quick sort... BUT it sure as heck would be a royal pain and depending on how it was done, might use more system resources in the end than a recursive function for large arrays. – Kenneth Mar 11 '11 at 22:46
  • so here's my attempt at factorial. to be fair I've seen this before, and although I wrote it from scratch, not memory, it is probably still easier than it would have been. Tried it in JS but had a parse error, but works in Python `def factorial(number): """return factorial of number""" if number == 0: return 0 elif number == 1: return 1 else: return number * factorial(number - 1)` – Andrew M Mar 11 '11 at 22:51
  • You've got it. I think the key with any recursive function is to work at developing a picture in your mind of what is happening (at least this is what I do). When I'm able to do this its very easy to understand it. One change I would make to your function is to have 0 return 1. 0! = 1. But that doesn't have anything to do with your recursion which is spot on! – Kenneth Mar 11 '11 at 22:56
  • Perhaps another thing to try would be to implement quicksort. There are probably more advance things that you could do as far as picking the pivot element but the simplest thing would be to just choose the first element as your pivot element and then get your two lists from there. – Kenneth Mar 11 '11 at 22:58
  • It almost seems like writing the recursions is easier than reading them, although maybe that's true only for simple problems. Starting with a breakpoint seems easy when you know what you're trying to do, and you know that you'll be building up to the recursive call itself; when you read someone else's code it's a bit counter-intuitive. Maybe cause you don't necessarily realize it is a recursive function until the last line. Perhaps my docstring should say '''return factorial of number, recursively'''. Thanks for your help. – Andrew M Mar 11 '11 at 23:01
  • No problem! Its a skill that take time and practice to develop. Hang in there and keep working at it. It'll get easier before you realize it! – Kenneth Mar 11 '11 at 23:04
2

Personally I think your best bet is through practice.

I learnt recursion with LOGO. You could use LISP. Recursion is natural in those languages. Otherwise you can liken it to the study of mathematical suites and series where you express what's next based on what came before, i.e. u(n+1)=f(u(n)), or more complex series where you have multiple variables and multiple dependencies, e.g. u(n)=g(u(n-1), u(n-2), v(n), v(n-1)); v(n)=h(u(n-1), u(n-2), v(n), v(n-1))...

So my suggestion would be that you find simple (in their expression) standard recursion "problems" and try and implement them in your language of choice. Practice will help you learn how to think, read and express those "problems". Note that often some of these problems can be expressed through iteration, but recursion might be a more elegant way to solve them. One of those is the calculation of factorial numbers.

Graphical "problems" I find make it easier to see. So look up Koch's flakes, Fibonacci, the dragon curve and fractals in general. But also look at the quick-sort algorithm...

You need to crash a few programs (endless loops, tentative use of infinite resources), and mishandle ending conditions (to get unexpected results) before you get your head around it all. And even when you get it you will still make those mistakes, just less often.

asoundmove
  • 1,667
  • 1
  • 9
  • 10
2

Structure and Interpretation of Computer Programs

It is the book used for learning, not just recursion, but programming in general at various universities. It is one of those foundational books that yields more information the more experience you gain and the more you read it.

dietbuddha
  • 8,677
  • 24
  • 36
0

As much as I like SICP and Gödel, Escher, Bach: an Eternal Golden Braid, Touretzky's LISP: A Gentle Introduction to Symbolic Computation also does a good job on introducing recursion.

The basic concept is this: First, you have to know when your recursive function is finished, so it can return a result. Then, you have to know how to take the unfinished case, and reduce it to something that you can recur on. For the traditional factorial(N) example, you're finished when N <= 1, and the unfinished case is N*factorial(N-1).

For a much uglier example, there's Ackermann's function A(m,n).

A(0,n) = n+1.                                   This is the terminal case.
A(m,0) = A(m-1,1) if m > 0.                     This is a simple recursion.
A(m,n) = A(m-1, A(m, n-1)) if m > 0 and n > 0.  This one is ugly.
John R. Strohm
  • 18,043
  • 5
  • 46
  • 56
0

I suggest playing around with some ML-style functional languages like OCaml or Haskell. I found that pattern-matching syntax really helped me understand even relatively complicated recursive functions, certainly much better than Scheme's if and cond statements. (I learned Haskell and Scheme at the same time.)

Here's a trivial example for contrast:

(define (fib n)
   (cond [(= n 0) 0]
         [(= n 1) 1]
         [else (+ (fib (- n 1)) (fib (- n 2)))]))

and with pattern matching:

fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

This example does not really do the difference justice--I never had problems with either version of the function. It's just to illustrate what the two options look like. Once you get to much more complex functions, using things like lists and trees, the difference becomes much more pronounced.

I particularly recommend Haskell because it's a simple language with very nice syntax. It also makes much easier to work with more advanced ideas like corecursion:

fibs = 0 : 1 : zipWith (+) fibs (drop 1 fibs)
fib n = fibs !! n

(You won't understand the above code until you play a bit with Haskell, but rest assured that it's basically magical :P.) Sure you could do the same with streams in Scheme, but it's much more natural in Haskell.

Tikhon Jelvis
  • 5,206
  • 1
  • 24
  • 20
0

It's out of print, but if you can find it, "Recursive Algorithms" by Richard Lorentz is about nothing but recursion. It covers the basics of recursion, as well as specific recursive algorithms.

The examples are in Pascal, but are not so large that the choice of language is bothersome.

Wayne Conrad
  • 1,118
  • 10
  • 20