Can you explain the concept of Recursion?

Question

If you had to explain recursion to a novice how would you do it?

Answer 1

If you don't get recursion, you should see this question for the answer

Answer 2

However, the recursion must have an end, otherwise it's an infinite loop.

So according to wikipedia:

Recursion, in mathematics and computer science, is a method of defining functions in which the function being defined is applied within its own definition. The term is also used more generally to describe a process of repeating objects in a self-similar way. For instance, when the surfaces of two mirrors are almost parallel with each other the nested images that occur are a form of recursion.

A simple examle, taken from said article, can be of the factorial function, which in C would be defined like so:

 unsigned int factorial(unsigned int n) 
 {
     if (n <= 1) return 1;
     return n * factorial(n-1);
 }

Answer 3

Recursion demonstrated as only David Hasselhoff can.

Answer 4

http://www.flickr.com/photos/nitot/2290128532/

Answer 5

Also, to understand recursion you have to understand recursion.

Answer 6

Now you're thinking with portals

Answer 7

Matryoshka dolls.

Answer 8

In fact, in mathematical systems recursion is often stated as an "axiom". So I am not sure if you even can define recursion in a rigorous way.

Answer 9

I read this one once, kind of liked it..

A child couldn't sleep, so her mother told her a story about a little frog,
    who couldn't sleep, so the frog's mother told her a story about a little bear,
        who couldn't sleep, so the bear's mother told her a story about a little weasel...
            who fell asleep.
        ...and the little bear fell asleep;
    ...and the little frog fell asleep;
...and the child fell asleep.

Source

Answer 10

Explain recursion in terms of conquer-and-divide.

If the person has not understood recursion, explain recursion, then come back to the current explanation.

Answer 11

Recursion is similar to loops : it has a start value an a target :

lets see this

     function int sum (int i, int n){ 
     if (i = 100)
        return n + 100; 
     else
        return sum(i+1,n+i);
     }

as you can see the code above is c++ simple code of a summing function from 0 to 100 you can call it by

sum(0,0);

there are basic rules when you write a recursive function usually you need to write a condition to know when to stop:

 if (i = 100)
    return n + 100;

also you need to let the function call itself while carrying the data that were calculated for each cycle.

return sum(i+1,n+i);

here is an example of calculating factory of an n .

 function int fact(int i, int n){ 
 if (i = 1)
    return n; 
 else
    return fact(i-1,n*i);
 }

you can call it like this

fact(6,1); // = 720
fact(4,1); // = 24

Answer 12

To explain recursion in programming, I'd keep it short and concrete, something like: Recursion in general means self-reference. The two common recursive things in programming are:

• Recursive methods, i.e. methods that call themself inside the method body
• Recursive data structures, e.g. a class that contains an instance of itself

Answer 13

Recursion: See recursion

Can't remember exactly where I saw that.

Answer 14

It might lead you to stackoverflowexception :)

Answer 15

function int sum (int i, int n){ 
     if (i = 100)
        return n + 100; 
     else
        return sum(i+1,n+i);
     }

reasonable enough for demonstration of recursion, however, this is also an example of brute force computing in the place of something that can be solved into a general formula with relatively simple mathematical methods.

i'm sure you're already well aware of this, and i'm just being pedantic, but the point still stands. the formula for a sum of consecutive integers is n(n+1)/2.

the proof of that formula is itself an excellent demonstration of the idea of recursion.

 S(n) = n*(n+1)/2 Prove by induction on n:

1) n=1 S(1) = 1 = 1*(1+1)/2 true for n = 1

2) Suppose true for n, where

S(n) = n*(n+1)/2 show that it's true

for n+1, i.e. show that S(n+1) = (n+1)(n=2)/2 Now S(n+1) = S(n) + n+1 = n(n+1)/2 + n+1 = (n+1)( n/2 + 1) = (n+1)(n + 2)/2 . . . done

 (proof as written by vlee1225 from Yahoo Answers)

thats a mathematical induction proof, and you can see the recursion demonstrated in step 2. the method asserts that the next term is defined in terms of adding something to the previous term. the rest of it is just algebra.

Answer 16

"To understand recursion, you must understand recursion" and "Recursion : see Recursion"

These two probably are the shortest representations of recursion I have ever seen and I love them both.

Recursion, simply put (and in programming) is a function that calls itself. This will result in a loop within a loop with an "escape hatch" or condition of sorts.

The last time I used a recursive search was to find all checked radio/option buttons inside a page but I was not to know if the control I am looking for is a child of another control. So the logic went as follows:

1. Select a parent/root control
2. Evaluate if this parent has child controls
3. Check if the child control is a radio button. Yes = check if ticked then exit the loop. No = treat this control as the parent control then go to step 1

And the first time I did recursion was with the old Towers of Hanoi assignment (ahhh.. the good old days)

Public Sub SolveHanoi(ByVal lNumMoves As Long, ByVal oBegin As cStack, ByVal oEnd As cStack, ByVal oTemp As cStack) If lNumMoves > 0 Then SolveHanoi lNumMoves - 1, oBegin, oTemp, oEnd oEnd.Push oBegin.Pop RaiseEvent StacksChanged(oBegin, oEnd) 'Debug.Print "Moved " & oEnd.Top & " from " & oBegin.Name & " to " & oEnd.Name SolveHanoi lNumMoves - 1, oTemp, oEnd, oBegin End If End Sub

And oh! yeah! a recursive search, when done incorrectly.. leads to a Stack Overflow (I just had to say it)