Multiple recursive functions

[Misbahu]

Hello there. I am new to c++ but not pretty new. I was reading a c++ book and I went across an example on recursive function along the way. There were some bunch of examples on recursion in the book, and I understand them pretty well until on this very one. The book doesn't explain very well on how the recursion works and it is confusing to someone like myself considering my c++ profile. The recursive function was designed to draw a ruler. The function called it self twice (That was where I got confused and also the two loop parts). Please I need someone out there to help explain to me how this works. I will be so grateful. I have the idiosyncrasy of "don't moving to next stage until you fully understand what's in the stage within which you are". Despite my bad English, I hope will understand my problem and help me out. Thanks

here is the code.
run it and see what it does

#include <iostream>

void subdevide(char rul[], int low, int high, int level);
int main()
{

const int len = 66;
const int div = 6;

char ruler[len];
int i;

for (i = 1; i <= len - 2; i++)
    ruler[i] = ' ';

int Max = len - 2;
int Min = 0;

ruler[Min] = ruler[Max] = '|';
cout << ruler << endl;
for (i = 1; i <= div; i++)
{
    subdevide(ruler, Min, Max, i);
    cout << ruler << endl;
    for (int j = 1; j < len - 2; j++)
        ruler[j] = ' ';
}
return 0;
}

Header.h
#ifndef HEADER_H
#define HEADER_H
void subdevide(char rul[], int low, int high, int level)
{
    using namespace std;
    if (level == 0)
        return;

    int mid = (high + low) /2;
    rul[mid] = '|';
    subdevide(rul, low, mid, level - 1);
    subdevide(rul, mid, high, level - 1);
}

#endif

[ats15]

Did you try to comment out one of the subdevide calls in your subdevide function?
Also, instead of the for loop on line 21 just do one step at a time.
In the first step, i=1, so you call your function with level=1. It will change the middle rul into '|', then calls subdevide onto the lower half, with level=0 (which won't do a thing), and on the upper half, once again with level=0
In step 2, it once again changes the middle, then calls subdevide on the lower half with level=1. So it will put '|' at the 1/4 and then it will stop since the calls to the first quarter and the second quarter are with level=0.Once this is finished, it will call subdevide on the upper half, with level=1. It will put '|' at the 3/4, then will call subdevide for the third quarter, then 4th quarter, with level=0.

And so on

[AbstractionAnon]

This is pretty straight forward.

Lines 13-14 set the ruler to spaces. There's a problem here because ruler[65] is not set to a null.

Lines 16-17 set min and max to 0 and 64. The choice of 64 as max is important as it is a power of 2.

Line 20 displays the ruler with begin and end marks. This may output additional garbage as ruler is treated as a null terminated string and no null was stored.

Lines 21-27 calls subdevide (correct english spelling is subdivide), displays the resulting ruler and then resets it to blanks and repeats until it has done this 6 times.

Lines 40-43 calculate the midpoint between high and low and place a marker at the midpoint. Since min and max are never changed, this will always be at 32 the first time subdevide is called. Now subdevide is called twice, once with low and mid and again with mid and high. The first time through the outter loop, subdevide will exit immediately since level is now 0 and the ruler will be printed with only the middle marker. The second time through the outter loop, subdevide will place the middle marker, then call itself twice, this time subdividing the two ruler segments, placing markers at 16 and 48. Third time through the outter loop, it repeats this process, but now calls itself again to place markers half way between 0 and 16, 16 and 32, 32 and 48, and 48 and 64. This splitting continues until the outter loop reaches 6 and the subdevide will be called 6 levels deep.

BTW, it's not a good idea to put executable code in a header file. If you were to include that header in multiple compilations, the linker would complain about multiple occurrances of the function.

It's also not a good idea to put using namespace std; inside a header file. This forces all including all including compilations to use the full std namespace, which may not be what you want. It belongs in your .cpp file.

[Misbahu]

Thanks so much guys. Your explanations do help. By following step by step your explanations and ats15 advice of doing just one step at a time on the line 21 loop, I grasp it. phew!! Thanks for the advice and correction AbtractionAnon. I also caught myself on providing the prototype of the function for int main() to use. I shouldn't do that since the function is in a header.h not an external.cpp. thanks once again and God bless.

[Misbahu]

Hey. I observed that when I comment out the loop on Line 25-26 I still got the same result like the one before I comment it out. If resetting the ruler to blank does not have effect on the ruler why is it there? If it does, what exactly does it reset and how does it do it?? And also by commenting out the very first loop that first reset the ruler to blank, I observed only two pieces (if I may refer to it as that) of the '|' on the Max part of the ruler are missing, but everything on the ruler appeared just fine. Why is it so important to reset the ruler to blank? Thanks

[ats15]

That step is initialization. Your compiler assigns the ' ' value to every element of the array. Most of the compilers will do that for you, but it is not guaranteed behavior. It is similar to int i;. Some compilers will assume i=0.

[LB]

@ats15: I don't know of any compiler which assigns the space character to every element of an array, not even in debug mode.

[ats15]

You are right. I should have said that is a non-printable character (ASCII code 0)