Thread: Recursion help

Read the tutorial on recursion.

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


"what recursion really is":

Code:

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

Hey! ("hi!");

hahah

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.

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]

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]

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]

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

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

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.