recursive function, might have inf loop

[Sevengraff]

I have to use a recursive function to print a ruler to the screen. it looks knida like this:

|       |       |
|   |   |   |   |
| | | | | | | | |
|||||||||||||||||

execept it will be about 65 characters long, and 7 lines deep.

here is my code:

// ruler.cpp
// ---------------------
// uses a recursive function to print a ruler to the screen

#include <iostream.h>

void subdivide( int lo, int hi, int level, char line[])
{
    if(level == '0')
        return;
    // get and mark midpoint
    int mid = (lo + hi) / 2;
    line[mid] = '|';
    // call again for left side
    subdivide(lo, mid-1, level-1, line);
    // call for right side
    subdivide(mid+1, hi, level-1, line);
    return;
    
}

int main( void )
{
    char line[66];
    int i;

    // prepair the array
    for(i=0; i<66; i++)
    {
        line[i] = ' ';
    }
    line[0] = '|';
    line[64] = '|';
    cout << line << "\n\n\n";
    for(i=0; i<7; i++)
    {
        subdivide(0, 65, i, line);
        cout << line << endl;
    }

    return 0;
} 

I dont get any errors when I compile it in VC++ 6, but when i run the exe it dies saying there is an error. when i try to use the debug thing, it says stack overflow. It all makes sense in my head, so i assume i have an infinate loop somewhere that i cant see because im a new programmer.
Can anyone help?

[kedaman]

There's an iterative solution to this as well,

for (int level=8;level>0;level/=2){
  for (int x=0;x<66;x++)
    cout << x%level?' ':'|';
  cout << endl;
}

[jim mcnamara]

Recursion is one of those things teachers think is cool, but is actually not even remotely useful to real application development, except in specially controlled conditions.

Here's why:
Every time a function calls itself:
It pushes all of the contents of the registers onto the stack, then
it pushes the contents of all of the local variables onto the stack.
Then it copies the parameters the function needs, and puts them on the stack, too. The function pops (reads) the stack -just the parameters only- when it is called. All of the other stuff remains on the stacks, and fills up the stack rapidly.

For this reason, recursion is very memory intensive, and tends to be extremely slow compared to an iterative solution (like Keds gave you).

Another major bad side to recursion is that reading your highly recursive code six months later is not easy - translation: it is hard to maintain. Even when you were the autho.

Lastly, you found out why recursion ii general is not a viable solution -stack overflow.

The only practical uses for recursion that I know about are writing descent parsers and some quicksort algorithms. And I've been writing code for a VERY long time.

This obviously is class work because, unless you're entering a contest, professional programmers usually don't do stuff like that. If you do, they stop paying you - if you get my drift. Teachers do not seem to know this fact...

[CornedBee]

I found recursion useful in hierarchical class object hierarchies (where the this pointer is the changing recursion parameter) useful too. That's also the only case I can think of where recursion is easier to understand than iteration.

[CornedBee]

Or similar situations. Basically whenever I have to visit every node of a tree I use iteration to visit siblings and recursion to walk through depth levels.

[kedaman]

Recursion is the way in declarative languages, since its much more wider concept than plain iteration. Recursion in imperative languages are just lowlevel and bound to hardware which is why programmers avoid it.