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.

This question already has an answer here:

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.

share|improve this question

marked as duplicate by MichaelT, gnat, BЈовић, Kilian Foth, Bart van Ingen Schenau Aug 1 '13 at 11:12

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.

2  
Recursion is just a function that calls itself inside it, what is your doubt? –  Dokkat Aug 1 '13 at 1:17
    
it's the inside part that's troubling me –  Khalid Ahmed Aug 1 '13 at 1:22
6  
Recursion is best understood by this link, though In plain English, what is recursion? works well too. –  MichaelT Aug 1 '13 at 1:30
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.) –  Eduardo León Aug 1 '13 at 2:15
8  
I find it always helps to have an example: programmers.stackexchange.com/questions/206745/… –  SomeKittens Aug 1 '13 at 2:16

1 Answer 1

up vote 9 down vote accepted

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, the 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".

share|improve this answer
    
so , basically, recursion is like a loop that calls itself in the loop while incrementing/decrementing it? –  Khalid Ahmed Aug 1 '13 at 2: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 1 '13 at 3: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 1 '13 at 10:49
1  
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 1 '13 at 15:35

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