# Having trouble understanding recursion [duplicate]

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.

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

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

• so , basically, recursion is like a loop that calls itself in the loop while incrementing/decrementing it? – KhalidGT 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
• @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
• 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