what - when to use recursion over iteration




What is recursion and when should I use it? (20)

  1. A function that calls itself
  2. When a function can be (easily) decomposed into a simple operation plus the same function on some smaller portion of the problem. I should say, rather, that this makes it a good candidate for recursion.
  3. They do!

The canonical example is the factorial which looks like:

int fact(int a) 
{
  if(a==1)
    return 1;

  return a*fact(a-1);
}

In general, recursion isn't necessarily fast (function call overhead tends to be high because recursive functions tend to be small, see above) and can suffer from some problems (stack overflow anyone?). Some say they tend to be hard to get 'right' in non-trivial cases but I don't really buy into that. In some situations, recursion makes the most sense and is the most elegant and clear way to write a particular function. It should be noted that some languages favor recursive solutions and optimize them much more (LISP comes to mind).

One of the topics that seems to come up regularly on mailing lists and online discussions is the merits (or lack thereof) of doing a Computer Science Degree. An argument that seems to come up time and again for the negative party is that they have been coding for some number of years and they have never used recursion.

So the question is:

  1. What is recursion?
  2. When would I use recursion?
  3. Why don't people use recursion?

1.) A method is recursive if it can call itself; either directly:

void f() {
   ... f() ... 
}

or indirectly:

void f() {
    ... g() ...
}

void g() {
   ... f() ...
}

2.) When to use recursion

Q: Does using recursion usually make your code faster? 
A: No.
Q: Does using recursion usually use less memory? 
A: No.
Q: Then why use recursion? 
A: It sometimes makes your code much simpler!

3.) People use recursion only when it is very complex to write iterative code. For example, tree traversal techniques like preorder, postorder can be made both iterative and recursive. But usually we use recursive because of its simplicity.


A recursive function is one which calls itself. The most common reason I've found to use it is traversing a tree structure. For example, if I have a TreeView with checkboxes (think installation of a new program, "choose features to install" page), I might want a "check all" button which would be something like this (pseudocode):

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

function checkRecursively(Node n) {
    n.Checked = True;
    foreach ( n.Children as child ) {
        checkRecursively(child);
    }
}

So you can see that the checkRecursively first checks the node which it is passed, then calls itself for each of that node's children.

You do need to be a bit careful with recursion. If you get into an infinite recursive loop, you will get a exception :)

I can't think of a reason why people shouldn't use it, when appropriate. It is useful in some circumstances, and not in others.

I think that because it's an interesting technique, some coders perhaps end up using it more often than they should, without real justification. This has given recursion a bad name in some circles.


An example: A recursive definition of a staircase is: A staircase consists of: - a single step and a staircase (recursion) - or only a single step (termination)


Consider an old, well known problem :

In mathematics, the greatest common divisor (gcd) … of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.

The definition of gcd is surprisingly simple:

where mod is the modulo operator (that is, the remainder after integer division).

In English, this definition says the greatest common divisor of any number and zero is that number, and the greatest common divisor of two numbers m and n is the greatest common divisor of n and the remainder after dividing m by n .

If you'd like to know why this works, see the Wikipedia article on the Euclidean algorithm .

Let's compute gcd(10, 8) as an example. Each step is equal to the one just before it:

  1. gcd(10, 8)
  2. gcd(10, 10 mod 8)
  3. gcd(8, 2)
  4. gcd(8, 8 mod 2)
  5. gcd(2, 0)
  6. 2

In the first step, 8 does not equal zero, so the second part of the definition applies. 10 mod 8 = 2 because 8 goes into 10 once with a remainder of 2. At step 3, the second part applies again, but this time 8 mod 2 = 0 because 2 divides 8 with no remainder. At step 5, the second argument is 0, so the answer is 2.

Did you notice that gcd appears on both the left and right sides of the equals sign? A mathematician would say this definition is recursive because the expression you're defining recurs inside its definition.

Recursive definitions tend to be elegant. For example, a recursive definition for the sum of a list is

sum l =
    if empty(l)
        return 0
    else
        return head(l) + sum(tail(l))

where head is the first element in a list and tail is the rest of the list. Note that sum recurs inside its definition at the end.

Maybe you'd prefer the maximum value in a list instead:

max l =
    if empty(l)
        error
    elsif length(l) = 1
        return head(l)
    else
        tailmax = max(tail(l))
        if head(l) > tailmax
            return head(l)
        else
            return tailmax

You might define multiplication of non-negative integers recursively to turn it into a series of additions:

a * b =
    if b = 0
        return 0
    else
        return a + (a * (b - 1))

If that bit about transforming multiplication into a series of additions doesn't make sense, try expanding a few simple examples to see how it works.

Merge sort has a lovely recursive definition:

sort(l) =
    if empty(l) or length(l) = 1
        return l
    else
        (left,right) = split l
        return merge(sort(left), sort(right))

Recursive definitions are all around if you know what to look for. Notice how all of these definitions have very simple base cases, e.g. , gcd(m, 0) = m. The recursive cases whittle away at the problem to get down to the easy answers.

With this understanding, you can now appreciate the other algorithms in Wikipedia's article on recursion !


Here's a simple example: how many elements in a set. (there are better ways to count things, but this is a nice simple recursive example.)

First, we need two rules:

  1. if the set is empty, the count of items in the set is zero (duh!).
  2. if the set is not empty, the count is one plus the number of items in the set after one item is removed.

Suppose you have a set like this: [x x x]. let's count how many items there are.

  1. the set is [x x x] which is not empty, so we apply rule 2. the number of items is one plus the number of items in [x x] (i.e. we removed an item).
  2. the set is [x x], so we apply rule 2 again: one + number of items in [x].
  3. the set is [x], which still matches rule 2: one + number of items in [].
  4. Now the set is [], which matches rule 1: the count is zero!
  5. Now that we know the answer in step 4 (0), we can solve step 3 (1 + 0)
  6. Likewise, now that we know the answer in step 3 (1), we can solve step 2 (1 + 1)
  7. And finally now that we know the answer in step 2 (2), we can solve step 1 (1 + 2) and get the count of items in [x x x], which is 3. Hooray!

We can represent this as:

count of [x x x] = 1 + count of [x x]
                 = 1 + (1 + count of [x])
                 = 1 + (1 + (1 + count of []))
                 = 1 + (1 + (1 + 0)))
                 = 1 + (1 + (1))
                 = 1 + (2)
                 = 3

When applying a recursive solution, you usually have at least 2 rules:

  • the basis, the simple case which states what happens when you have "used up" all of your data. This is usually some variation of "if you are out of data to process, your answer is X"
  • the recursive rule, which states what happens if you still have data. This is usually some kind of rule that says "do something to make your data set smaller, and reapply your rules to the smaller data set."

If we translate the above to pseudocode, we get:

numberOfItems(set)
    if set is empty
        return 0
    else
        remove 1 item from set
        return 1 + numberOfItems(set)

There's a lot more useful examples (traversing a tree, for example) which I'm sure other people will cover.


In plain English, recursion means to repeat someting again and again.

In programming one example is of calling the function within itself .

Look on the following example of calculating factorial of a number:

public int fact(int n)
{
    if (n==0) return 1;
    else return n*fact(n-1)
}

In plain English: Assume you can do 3 things:

  1. Take one apple
  2. Write down tally marks
  3. Count tally marks

You have a lot of apples in front of you on a table and you want to know how many apples there are.

start
  Is the table empty?
  yes: Count the tally marks and cheer like it's your birthday!
  no:  Take 1 apple and put it aside
       Write down a tally mark
       goto start

The process of repeating the same thing till you are done is called recursion.

I hope this is the "plain english" answer you are looking for!


Recursion as it applies to programming is basically calling a function from inside its own definition (inside itself), with different parameters so as to accomplish a task.


Recursion is a method of solving problems based on the divide and conquer mentality. The basic idea is that you take the original problem and divide it into smaller (more easily solved) instances of itself, solve those smaller instances (usually by using the same algorithm again) and then reassemble them into the final solution.

The canonical example is a routine to generate the Factorial of n. The Factorial of n is calculated by multiplying all of the numbers between 1 and n. An iterative solution in C# looks like this:

public int Fact(int n)
{
  int fact = 1;

  for( int i = 2; i <= n; i++)
  {
    fact = fact * i;
  }

  return fact;
}

There's nothing surprising about the iterative solution and it should make sense to anyone familiar with C#.

The recursive solution is found by recognising that the nth Factorial is n * Fact(n-1). Or to put it another way, if you know what a particular Factorial number is you can calculate the next one. Here is the recursive solution in C#:

public int FactRec(int n)
{
  if( n < 2 )
  {
    return 1;
  }

  return n * FactRec( n - 1 );
}

The first part of this function is known as a Base Case (or sometimes Guard Clause) and is what prevents the algorithm from running forever. It just returns the value 1 whenever the function is called with a value of 1 or less. The second part is more interesting and is known as the Recursive Step . Here we call the same method with a slightly modified parameter (we decrement it by 1) and then multiply the result with our copy of n.

When first encountered this can be kind of confusing so it's instructive to examine how it works when run. Imagine that we call FactRec(5). We enter the routine, are not picked up by the base case and so we end up like this:

// In FactRec(5)
return 5 * FactRec( 5 - 1 );

// which is
return 5 * FactRec(4);

If we re-enter the method with the parameter 4 we are again not stopped by the guard clause and so we end up at:

// In FactRec(4)
return 4 * FactRec(3);

If we substitute this return value into the return value above we get

// In FactRec(5)
return 5 * (4 * FactRec(3));

This should give you a clue as to how the final solution is arrived at so we'll fast track and show each step on the way down:

return 5 * (4 * FactRec(3));
return 5 * (4 * (3 * FactRec(2)));
return 5 * (4 * (3 * (2 * FactRec(1))));
return 5 * (4 * (3 * (2 * (1))));

That final substitution happens when the base case is triggered. At this point we have a simple algrebraic formula to solve which equates directly to the definition of Factorials in the first place.

It's instructive to note that every call into the method results in either a base case being triggered or a call to the same method where the parameters are closer to a base case (often called a recursive call). If this is not the case then the method will run forever.


Recursion is solving a problem with a function that calls itself. A good example of this is a factorial function. Factorial is a math problem where factorial of 5, for example, is 5 * 4 * 3 * 2 * 1. This function solves this in C# for positive integers (not tested - there may be a bug).

public int Factorial(int n)
{
    if (n <= 1)
        return 1;

    return n * Factorial(n - 1);
}

Recursion is the process where a method call iself to be able to perform a certain task. It reduces redundency of code. Most recurssive functions or methods must have a condifiton to break the recussive call i.e. stop it from calling itself if a condition is met - this prevents the creating of an infinite loop. Not all functions are suited to be used recursively.


Recursion works best with what I like to call "fractal problems", where you're dealing with a big thing that's made of smaller versions of that big thing, each of which is an even smaller version of the big thing, and so on. If you ever have to traverse or search through something like a tree or nested identical structures, you've got a problem that might be a good candidate for recursion.

People avoid recursion for a number of reasons:

  1. Most people (myself included) cut their programming teeth on procedural or object-oriented programming as opposed to functional programming. To such people, the iterative approach (typically using loops) feels more natural.

  2. Those of us who cut our programming teeth on procedural or object-oriented programming have often been told to avoid recursion because it's error prone.

  3. We're often told that recursion is slow. Calling and returning from a routine repeatedly involves a lot of stack pushing and popping, which is slower than looping. I think some languages handle this better than others, and those languages are most likely not those where the dominant paradigm is procedural or object-oriented.

  4. For at least a couple of programming languages I've used, I remember hearing recommendations not to use recursion if it gets beyond a certain depth because its stack isn't that deep.


Simple english example of recursion.

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.

This is an old question, but I want to add an answer from logistical point of view (i.e not from algorithm correctness point of view or performance point of view).

I use Java for work, and Java doesn't support nested function. As such, if I want to do recursion, I might have to define an external function (which exists only because my code bumps against Java's bureaucratic rule), or I might have to refactor the code altogether (which I really hate to do).

Thus, I often avoid recursion, and use stack operation instead, because recursion itself is essentially a stack operation.


To recurse on a solved problem: do nothing, you're done.
To recurse on an open problem: do the next step, then recurse on the rest.


Whenever a function calls itself, creating a loop, then that's recursion. As with anything there are good uses and bad uses for recursion.

The most simple example is tail recursion where the very last line of the function is a call to itself:

int FloorByTen(int num)
{
    if (num % 10 == 0)
        return num;
    else
        return FloorByTen(num-1);
}

However, this is a lame, almost pointless example because it can easily be replaced by more efficient iteration. After all, recursion suffers from function call overhead, which in the example above could be substantial compared to the operation inside the function itself.

So the whole reason to do recursion rather than iteration should be to take advantage of the call stack to do some clever stuff. For example, if you call a function multiple times with different parameters inside the same loop then that's a way to accomplish branching . A classic example is the Sierpinski triangle .

You can draw one of those very simply with recursion, where the call stack branches in 3 directions:

private void BuildVertices(double x, double y, double len)
{
    if (len > 0.002)
    {
        mesh.Positions.Add(new Point3D(x, y + len, -len));
        mesh.Positions.Add(new Point3D(x - len, y - len, -len));
        mesh.Positions.Add(new Point3D(x + len, y - len, -len));
        len *= 0.5;
        BuildVertices(x, y + len, len);
        BuildVertices(x - len, y - len, len);
        BuildVertices(x + len, y - len, len);
    }
}

If you attempt to do the same thing with iteration I think you'll find it takes a lot more code to accomplish.

Other common use cases might include traversing hierarchies, e.g. website crawlers, directory comparisons, etc.

Conclusion

In practical terms, recursion makes the most sense whenever you need iterative branching.


You want to use it anytime you have a tree structure. It is very useful in reading XML.


hey, sorry if my opinion agrees with someone, I'm just trying to explain recursion in plain english.

suppose you have three managers - Jack, John and Morgan. Jack manages 2 programmers, John - 3, and Morgan - 5. you are going to give every manager 300$ and want to know what would it cost. The answer is obvious - but what if 2 of Morgan-s employees are also managers?

HERE comes the recursion. you start from the top of the hierarchy. the summery cost is 0$. you start with Jack, Then check if he has any managers as employees. if you find any of them are, check if they have any managers as employees and so on. Add 300$ to the summery cost every time you find a manager. when you are finished with Jack, go to John, his employees and then to Morgan.

You'll never know, how much cycles will you go before getting an answer, though you know how many managers you have and how many Budget can you spend.

Recursion is a tree, with branches and leaves, called parents and children respectively. When you use a recursion algorithm, you more or less consciously are building a tree from the data.


"If I have a hammer, make everything look like a nail."

Recursion is a problem-solving strategy for huge problems, where at every step just, "turn 2 small things into one bigger thing," each time with the same hammer.

Example

Suppose your desk is covered with a disorganized mess of 1024 papers. How do you make one neat, clean stack of papers from the mess, using recursion?

  1. Divide: Spread all the sheets out, so you have just one sheet in each "stack".
  2. Conquer:
    1. Go around, putting each sheet on top of one other sheet. You now have stacks of 2.
    2. Go around, putting each 2-stack on top of another 2-stack. You now have stacks of 4.
    3. Go around, putting each 4-stack on top of another 4-stack. You now have stacks of 8.
    4. ... on and on ...
    5. You now have one huge stack of 1024 sheets!

Notice that this is pretty intuitive, aside from counting everything (which isn't strictly necessary). You might not go all the way down to 1-sheet stacks, in reality, but you could and it would still work. The important part is the hammer: With your arms, you can always put one stack on top of the other to make a bigger stack, and it doesn't matter (within reason) how big either stack is.







computer-science