0

I have just started learning about recursion but I'm having a hard time understanding it. Please would you recommend any links or books that explain recursion in detail.

FizzyTea
  • 105
  • 5
KhalidGT
  • 27
  • 4
  • 2
    Recursion is just a function that calls itself inside it, what is your doubt? – MaiaVictor Aug 01 '13 at 01:17
  • it's the inside part that's troubling me – KhalidGT Aug 01 '13 at 01:22
  • 8
    Recursion is best understood by [this link](http://programmers.stackexchange.com/questions/206745/having-trouble-understanding-recursion), though [In plain English, what is recursion?](http://programmers.stackexchange.com/questions/25052/in-plain-english-what-is-recursion?) works well too. –  Aug 01 '13 at 01:30
  • [SICP](http://mitpress.mit.edu/sicp/full-text/book/book.html) explains recursion. So does Google. – FizzyTea Aug 01 '13 at 02:09
  • 1
    You guys are getting it horribly wrong. Recursion is the computational use of a structure's induction principle. (Regardless of whether a self-call takes place or not.) – isekaijin Aug 01 '13 at 02:15
  • 10
    I find it always helps to have an example: http://programmers.stackexchange.com/questions/206745/having-trouble-understanding-recursion – SomeKittens Aug 01 '13 at 02:16
  • Recursion is all about guaranteeing that the self-calls (if any take place) will end at some point, because a base case will be reached. Also, stop with the self-link jokes; first, they are not funny; second, if anything, that is an example of corecursion, which guarantees productivity, not finiteness. – isekaijin Aug 01 '13 at 02:24
  • 1
    @EduardoLeón: You don't have to have a base case. `def repeat_infinitely(body) = { body(); repeat_infinitely(body) }` is a perfectly valid (tail-)recursive procedure and, for example, a nice way to implement an event loop or a web server in language without loops. As you point out, an even nicer way to implement the same thing would be as corecursion over codata, even allowing the concept of "infinite loop" in a non-Turing-complete Total Functional Programming Language, but the recursive formulation (even if it actually implements corecursion) is not inherently bad. – Jörg W Mittag Aug 01 '13 at 11:31

1 Answers1

10

Start with a piece of paper that has the number 1 on it and the phrase "change the number by adding one". Do what is written on the piece of paper.

That quote is our function:

count = 1
def function():
    global count
    count += 1

Modify the note (our function) to say: "change the number by adding one, then do what is written on the note". Do what is literally on the piece of paper - change the number, then do what is written on the paper, which is to change the number and do what is on the paper, which is to change the number and do what is on the paper, ...

Again, that quote is our function:

count = 1
def function(): 
    global count
    count += 1 
    function() # <- this is what makes this function recursive
               # ie: "do what is written on the paper"

That's infinite recursion. When you call the function, it does something, and then it calls itself.

Practical recursion says you need some sort of condition to tell you when to stop. To do that, change what's on the note to read "Change the number by adding one. If the number is less than 100, then do what is written on the paper". Again, that quote is our function:

count = 1
def function():
    global count
    count += 1
    if (count < 100):
        function()

Generally speaking, every proper recursive function needs some sort of terminal condition -- a test that prevents the function from calling itself forever.

Write on a piece of paper "Change the number by adding one, then do what is written on this paper". Put that piece of paper in your pocket as a reminder of what recursion is.

Note: the fact that the example increments a number is not at all related to recursion in general. It's just a simple way to represent "doing some work". A recursive function doesn't necessarily have to increment or decrement a counter. All it needs is some way to determine when there is no more work to be done.

If you still don't understand what recursion is, read this answer to the question "Having trouble understanding recursion".

Bryan Oakley
  • 25,192
  • 5
  • 64
  • 89
  • so , basically, recursion is like a loop that calls itself in the loop while incrementing/decrementing it? – KhalidGT Aug 01 '13 at 02:22
  • +1 for recursive linking. On a side note, usually recursive has these conditions: 1. Call to the same function, 2. Has termination condition, 3. usually has increment / decrement in some way (i++ / moveNext/movePrev) – Fendy Aug 01 '13 at 03:08
  • 1
    @KhalidAhmed: the increment/decrement isn't a requirement per se, it's just in the example for illustrative purposes. Usually a recursive function does _something_, and then it has some sort of test to decide whether to continue or to stop. – Bryan Oakley Aug 01 '13 at 10:49
  • 2
    Yeah, i would NOT mention increment/decrement as part of explaining recursion. Simple that recursive functions typically inspect some type of data element to decide to continue recursing or not, otherwise you'll have an infinite loop, which is usually a bad thing. – Graham Aug 01 '13 at 15:35