Recursion help

Hi

Can anyone explain to me what recursion really is why and where you would use it - if possible why would you use it rather than a loop cause that is all i am aware of what it does at the moment saying that it is similar to a loop.

can anyone help?

Thanks

Read the tutorial on recursion.

fractals :D ... linked lists... trees of all sorts... etc...


"what recursion really is":

Code:

---

void Hey! (string hi)
{
        cout << hi << endl;
        Hey! (hi);
}

Hey! ("hi!");

---

hahah :D

recursion is a loop... it might just make the code a lot cleaner... i hear it's not as efficient as other loops maybe? i forget, i made a thread on it once... i'll try and go dig it up.

Do you know what a tree looks like? I'm referring to a tree in computing, not a real tree. Maybe something like this:

Code:

---

                      a
                    / | \
                    b  c  d
                  / \    \
                  e  f    g
                /  / \  / \
                h  i  j k  l

---

Now, let's say you want to process the nodes of the tree. One easy way to break it down is to start at the root, and process each of the root's subtree's. So from a, you have these three subtrees:

Code:

---

                    b          c          d
                  / \                    \
                  e  f                    g
                /  / \                  / \
                h  i  j                k  l

---

It should be easy to process c, you just do what you need to do with that node. But how do you process b? Again, separating each subtree makes sense, so you have:

Code:

---

                  e        f
                /        / \
                h        i  j

---

Notice how the task keeps getting broken down into smaller and smaller task, but each smaller task is handled the same way as the big task. If the root node has children, process the children, then process the node. When you write the code, it just makes sense to have a function that does that and doesn't care whether it is working on the whole tree or a subtree. It will just keep recursing on smaller and smaller subtrees until it finishes the whole thing.

That's what recursion is for. When you can break a problem down into smaller, identical problems.

Quote:

---

Originally Posted by simpleid

recursion is a loop... it might just make the code a lot cleaner... i hear it's not as efficient as other loops maybe?

---

this will crash:

Code:

---

#include <iostream>
#include <string>

void Hey(std::string hi)
{
    std::cout << hi << std::endl;
    Hey(hi);
    return;
}

int main()
{
    Hey("hi!");
    return 0;
}

---

this doesn't:

Code:

---

#include <iostream>
#include <string>

void Hey(std::string hi)
{
    while (1)
        std::cout << hi << std::endl;
    return;
}

int main()
{
    Hey("hi!");
    return 0;
}

---

Not neccesarily. Some compilers can actually optimise recursive functions into iterative loops, or so I hear.
[edit]

Quote:

---

Question #49

When run on a computer, will a recursive function without an end condition ever quit?
Compiler-Specific (Some compilers can convert these functions to infinite loops)
No
Yes

---

From http://www.cprogramming.com/ans/ans5.html [/edit]

Besides, neither should compile, unless you include <string>. And use std::cout, std::endl, and std::string, or a using directive or three.

[edit=2] As for efficiency . . . iterative loops are generally considered to be more efficient than recursive functions. With recursive functions, there's a speed hit as the function is called, and of course memory usage on the stack as a result, with extra memory usage if the function has any local variables.

However, sometimes an iterative solution to a problem might be so convoluted or inefficient or hard to read that a recursive solution might be better.

Personally, I don't see anything wrong with writing recursive functions if they solve a problem easily. (Unless the iterative solution is very trivial.) You can always try an iterative solution later. [/edit]

Quote:

---

Not neccesarily. Some compilers can actually optimise recursive functions into iterative loops, or so I hear.

---

Tail recursion as in robwhit's example is easy to transform into a loop even for a human, so any optimising compiler should include it.

[edit] Okay, robwhit just deleted a rather insulting (sorry) post saying something like "lol, I know it would crash, I wasn't expecting anyone to stick my code into a real program." Hence the remainder of this post. [/edit]

That's the point. It might not crash. If your compiler can optimise that recursive function into an infinite iterative loop, and you have compiler optimisations enabled, then it will act like an infinite loop, and will never segfault or whatever.

Besides, it depends on your definition of crash. With large percentage of my programs, an infinite loop would be considered a crash. ;)

[edit]

Quote:

---

Last edited by robwhit : Today at 01:05 PM. Reason: dwks -

---

That's pretty funny . . . :D [/edit]

Quote:

---

Originally Posted by dwks

[edit] Okay, robwhit just deleted a rather insulting (sorry) post saying something like "lol, I know it would crash, I wasn't expecting anyone to stick my code into a real program." Hence the remainder of this post. [/edit]

---

what? no I didn't.

in fact I think it's good that you corrected me. I'd rather people correct me on little things especially, so I don't trip up on them later.

Quote:

---

what? no I didn't.

---

Someone did -- I didn't see who -- and from the way it was written I assumed it was the original author of the post in question. That is, you. I must have been mistaken. My apologies.

Recursion really isn't a loop. You could say, any loop is a subset of recursion. Any loop of the form...

Code:

---

loop(N) {
  for (i = 0; i < N; ++i) {
      fn(i);
  }
}

---

Could be expressed recursively as

Code:

---

recurse(N) {
  recurse(N - 1);
  fn(N);
}

---

To really get into what recursion entails sort of involves some CS theory, but a good working definition is "A Recursive Function is Defined in Terms of Itself". A recursive function is very analogous to a mathematical proof that uses induction.


A friend and I were messing around with server code for an open source game, long ago. The code which caused an enemy to 'aggro' one of the players was killing it (the game was quite fast otherwise). Our solution was thus:

How to check an area for aggro...

• Split the map into four quadrants.
• For each quadrant without players, ignore it.
• For each quadrant with players, check that quadrant for aggro.

Code:

---

// aggro_mobs(area) is slow when area is large,
// So split it into smaller areas.
Check_Aggro (RECT area) {
  if (contains_players(curr_quad) == FALSE)
      // Quad contains no players, abort.
      return;

  if (area.x < MIN_RESOLUTION_SIZE) {
      // We've zoomed in closely enough, let the mobs aggro.
      aggro_mobs (area);
      return;
  }

  // Area is too big, but not empty.  Break it down.
  Check_Aggro (NORTHWEST_QUAD(curr_quad));
  Check_Aggro (SOUTHWEST_QUAD(curr_quad));
  Check_Aggro (NORTHEAST_QUAD(curr_quad));
  Check_Aggro (SOUTHEAST_QUAD(curr_quad));
}

---

This could fundamentally not be done only using a loop.

@QuestionC:
Essentially a type of quad tree test. It would be very hard and awkard to implement a quad-tree without using recursion.


The cost of the function call and the stack is minimal so long as you don't recurse too far before returning which will cause a stack overflow. I would not bang my head against a wall trying to implement a recursive function iteratively rather than recursively unless the recursive version will cause a stack overflow.

Writing a floodfill algorithm is one such case. The recursive floodfill works but it will certainly overflow the stack at some point. This almost has to be implemented iteratively which is quite ugly and awkward.

So it doesn't come down to a simple right way or wrong way but the best way for the problem at hand.