0

Good morning everyone,

The library will be home, 0800 till 2100. I've been working on trying my loops in my hailstone sequence into recursions. It seem recursion can easrier to do, instead of creating loops. I say seem, because now I have come to halt on my progress. The halt is in the form of my sequence_Max function:

/*
//sequence_Max(int n)
//Returns the largest value in the
//hailstone sequence starting at 'n'.
*/
int sequence_Max(int n)
{
    //Variable Declaration.
    int max = n, temp = n;

    while (temp > 1)
    {
        temp = next(temp);
        if(temp > max)
        {
            max = temp;
        }
    }
    return max;
}

It was a pain in the neck coming up with a loop (I recieved a lot of help from individuals on this site) for it, but now I have to change the loop into a recursion. The only practice that I have up to this point with recursion is in the hailstone_Sequence and sequence_Length functions.

Below is my program thus far (I don't have to moditfy the the next or main functions):

// Tab stops:  4

//The program executes a number of functions to print their
//values with a list of sentences.

#include <iostream>
#include <cstdio>
using namespace std;

//Function Prototype Declaration
int next(int), sequence_Length(int), sequence_Max(int), sequence_Comparison(int),
    initialcomp_Num(int);

void hailstone_Sequence(int);

int main (int argc, char** argv)
{
    int user_Input;

    cout << "What number shall I start with? ";
    cin >> user_Input;
    cout << user_Input << "\n";

    cout << "The hailstone sequence starting at " << user_Input << " is: " << endl;
    hailstone_Sequence(user_Input);

    cout << "\nThe length of the sequence is " << sequence_Length(user_Input);
    cout << ".\n";

}

/*
//next(int n)
//Returns a number
//that follows 'n' in the sequence.
*/
int next(int n)
{
    if (n > 1)
    {
        if ((n % 2) == 0)
        {
            return n / 2;
        }
        else
        {
            return  3 * n + 1;
        }
    }
   return n;

}

/*
//hailstone_Sequence(int n)
//Prints the entire sequence beginning with 'n'.
*/
void hailstone_Sequence(int n)
{
    //Variable Declaration.
    int temp = n;

    //Base case.
    if (n == 1)
    {
        cout << 1;
    }

    else if (n > 1)
    {

        cout << n << " ";
        hailstone_Sequence(next(n));

    }
}

/*
//sequence_Length(int n)
//Returns the output length of
//the hailstone sequence.
*/
int sequence_Length(int n)
{
    int count = next(n);

    //Special case statement. 
    if (n == 1)
    {
        return 1;
    }

    //Determines the length of the sequence until
    //n is equal to 1 (base case). 
    else if (count >= 1) 
    {
        count;
        return 1 + sequence_Length(count);
    }
}

/*
//sequence_Max(int n)
//Returns the largest value in the
//hailstone sequence starting at 'n'.
*/
int sequence_Max(int n)
{
    //Variable Declaration.
    int max = n, temp = n;

    while (temp > 1)
    {
        temp = next(temp);
        if(temp > max)
        {
            max = temp;
        }
    }
    return max;
}

/*
//sequence_Comparison(int n)
//Returns the integer with the longest hailstone
//sequence starting from 1 to 'n'.
*/
int sequence_Comparison(int n)
{
    //Variable Declaration.
    int count, top, aftertop;

    if ( n <= 1)
    {
        return n;
    }

    top = sequence_Length(n);
    for (count = 1; count != n; count++)
    {
        if (top < sequence_Length(count))
        {
            aftertop = sequence_Length(count);
            top = aftertop;
        }
    }
    return top;
}

/*
//initialcomp_Num(int n)
//Returns the starting value
//of the longest sequence that starts on a value from
//1 to 'n'.
*/
int initialcomp_Num(int n)
{
    //Variable Declaration.
    int count, initial, topValue, cal;

    //Function will work as intended if 'n' is not less than 1.
    if (n <= 1)
    {
        return n;
    }
    initial = sequence_Length(n);
    topValue = n;
    for (count = 1; count != n; count++)
    {
        cal = sequence_Length(count);
        //max(initial, cal)

        if (initial <= cal)
        {
            //initial = cal;
            topValue = count;
        }
        else if (initial >= cal)
        {
            topValue = topValue;
        }
    }
    return topValue;
}

Limitations
a). No function is allowed to change the value of any variable, once that variable has been given a value.

To get started with the sequence_Max function, should I look into using a max(x,y) calculation?

v/r

Edited by Sherwin_4

3
Contributors
29
Replies
139
Views
9 Months
Discussion Span
Last Post by JamesCherrill
Featured Replies
  • Consider n = 9 (it could be any positive integer). Hailstone sequence is as follows... `9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1` Split this into 2 pieces (first element, remaining elements), like so. 1. `9` 2. `28 … Read More

  • It is indeed "he". And you taught me a new word. "Hir"! Read More

  • Cast your mind back a day or so when you were making great progress by starting with a short pseudo-code text description of the process and some pencil and paper simulation to check it out. You seem to have forgotten about that and are hacking code that frankly makes no … Read More

  • > You can call it a guard or you can call it a base case, but there's no reason to have a guard AND a base case. If you find yourself needing both, you probably have a design flaw. I respectfully disagree. A guard protects the following code from incorrect … Read More

  • Last post from me in this thread. I won't have time to log into Daniweb for at least a week, so I am posting the code that I sent Sherwin via PM below before I forget. Sherwin, if you don't want to see the code yet, stop reading this post. … Read More

1

Consider n = 9 (it could be any positive integer). Hailstone sequence is as follows...

9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Split this into 2 pieces (first element, remaining elements), like so.

  1. 9
  2. 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Maximum of 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 is 52. Return max(9, 52), which is 52.

Note that 28 is next(9).

In other words, to get the maximum value of ANY sequence, you can take the maximum of the FIRST element and the maximum of the remaining elements, so take the maximum of 9 and sequence_Max(28), which is the maximum of n and sequence_Max(next(n)). Your base case (you always have a base case using recursion) is when n is 1, so check for that at the top. Return 1 in that case.

0

Here is what I came up with:

int sequence_Max(int n)
{
    //Variable Declaration.
    int high = n, low = next(n);
    if (n <= 1)
    {
        return 1;
    }

    //Base case.
    else if (n != 1)
    {
        int result = max(low, high);

        return sequence_Max(result);
    }

}

I'm running into the problem of keeping this going by calling on the same function from within.

0

You have the recursive call to next on line 4, which is before you test for n<=1 and terminate the recursion, so it always recurses while initialising the variables, even if n<=1.

<EDIT> Above comment is wrong - I left it here so subsequent posts still make sense.. Mea Culpa. JC </EDIT>

In any recursion you must deal with the terminating condition before you make any recursive calls

(and the n!=1 test is redundant, because you have already reurned from the method on line 7 if n==1)

Edited by JamesCherrill

0

Sorry sorry sorry. Looking back at that post I wonder what I was thinking! Please ignore it. I'm sorry if it distracted you. I knew what it should look like, and forced what I saw into that shape, even though it was nothing like. Put it down to a "senior moment"!

AsserNull didn't suffer any such brain damage. Please re-read his post. The description of the algorithm in his last para is correct, and it's what you need.

to get the maximum value of ANY sequence, you can take the maximum of the FIRST element and the maximum of the remaining elements... which is the maximum of n and sequence_Max(next(n)). Your base case.. is when n is 1, so check for that at the top. Return 1 in that case.

Re-phrasing that in pseudo-code:

if (n<=1) return 1
return max (n, sequence_Max(next(n))

Your code is a lot more complicated than that, and I have no idea why.

0

Wow, I didn't know I could call it like that. My problem (among other things) in regards to this situation, is not knowing what I'm unable to do and what I can do. I can't believe how simple this function coding is.

0

I'm now doing hand simualtion for that function. I'm currently having an inception moment.

so n = 8
8 <=1, no
max is then (8, 4)

so n = 2
2 <= 1, no
max is then (4, 2) and so on (I believe that once it gets to one, then compares numbers at the point back to the first iteration)

I'm I looking at this correctly? Also, the base case would be in next(int n) right? If the base case was in sequence_Max function of n<=1, then you would only return 1 and not the max.

0

I don't see where that so n=2 came from!
Let's use 9, because I have the sequence for that..

n= 9
not <=1
return max (9, seqMax(next(9)))  // next(9) is 28, so this is max(9, seqMax(28))
    1st recursion: 
    n = 28
    not <= 1
    return max (28, seqMax(next(28)))  // this is max(9, seqMax(14))
        2nd recursion:
        n = 14
        return max (14, seqMax(next(14)))  // this is max(9, seqMax(7))
               lots more recursion until eventually we get seqMax(2)
                     n = 2
                     return max (2, seqMax(next(2)))  // this is max(9, seqMax(1))
                           last recursion
                           n=1
                           return 1
                     can now return max(2,1) ie 2
               lots more returns getting 40 in the process
        can now return max(14.40) ie 40
   can now return max(28, 40) 
can now return max(9, 40)

The base case is n=1, returns 1 without recursing, which then enables the whole recursive stack to unwind

Edited by JamesCherrill

0

I was doing a hand simulation. I just picked a random number to start off with.

0

ps Doing a hand simulation is exactly the right thing to do. Recursion always twists your brain into prezels, and going straight to code is asking for a mess. We are always saying it in these forums - if there's the slightest doubt about what the code should be doing, do it on paper first - but most beginners are too impatient so end up wasting more time.
I would just say - don't just simulate with some random numbers. Start with some real data where you know the correct answer before you start simulating, so you know when you have got it right.
Anyway - well done.

0

Wow, I didn't know I could call it like that. My problem (among other things) in regards to this situation, is not knowing what I'm unable to do and what I can do. I can't believe how simple this function coding is.

Yep. Two lines. However, you might consider making it longer in order to break it into each little step. An experienced programmer will write it as James did. There's a potential downside to doing it that way as a newbie. If you have a bug somewhere, it can be easier to track it down if you don't have a compound statement as James does. Again, I would write it as James did, but I didn't start out that way. And in my current coding, I often write it as James did, then when I find a bug, I will break it into smaller pieces till I find the bug, then when I have it debugged, I will revert back to the two-line version. So let's start with the two line version...

if (n<=1) return 1;
return max (n, sequence_Max(next(n));

There isn't much to the first line, so leave it as is. But let's say something isn't working in that second line. I look at this line and I see at least three POTENTIAL things that could be a bug.

return max (n, sequence_Max(next(n));
  1. The max function could be wrong (doubtful since it's part of the C++ standard. The odds of them writing a bad max function are very low. But never assume. There is also a possibility that I think I am calling C++'s max function, but I really am not, or vice-versa. That's called a "namespace" issue. You are using the standard namespace, but consider the fact that your original function had a VARIABLE called max. Or what if you had a second function called max? Or what if you didn't include the correct library? Or if you forgot the "using namespace std" line? Etcetera, etcetera. Don't worry too much about namespaces now. You'll get to them much later. My point is that when debugging, you have to figure out all the things that MIGHT have gone wrong and systematically figure out which one it is. In this line, there are three functions that could be the culprit.
  2. The next function might be wrong.
  3. My current function (sequence_Max) is wrong.
  4. Something else might be wrong.

So let's break this two-line function into more than two lines. If we do that, we have th option of sticking some cout statements in there to make sure that what we THINK is happening is actually happening. We can also stick some cin.get() lines in there to pause the program if desired. We can't do that if it's just two lines. Make sure to take those lines OUT after you're done with them.

Also note the descriptive variable names.. high, low, and temp are not very descriptive in this function. Even worse is that high and low might actually be COUNTER-intuitive in that low might be bigger than high.

int sequence_Max(int n)
{
    // base case;
    if(n <= 1)
        return 1;

    int firstValue = n;
    int nextValue = next(n);
    int maxNotIncludingFirstValue = sequence_Max(nextValue);
    int maxIncludingFirstValue = max(firstValue, maxNotIncludingFirstValue);
    return maxIncludingFirstValue;
}

Now look how easy it is to add some statements in there (that will be taken out later) to really see what is going on. The cin.get() line makes it pause at the top. Press Enter to continue each time (note it won't pause the FIRST time through. Don't worry about why for now. It has to do with how cin works. Just press Enter when it does pause to make it continue).

int sequence_Max(int n)
{
    cout << endl << endl << endl << endl << "Entering sequenceMax -- n = " << n << endl;
    cin.get(); // pausing.  Press Enter to continue.

    // base case;
    if(n <= 1)
    {
        cout << "sequence_Max: base case met.  Leaving sequence_Max.  Returning 1\n";
        return 1;
    }

    cout << "sequence_Max: Base case NOT met -- n = " << n << endl;

    int firstValue = n;
    int nextValue = next(n);

    cout << "firstValue = " << firstValue << " nextValue = " << nextValue << endl;

    int maxNotIncludingFirstValue = sequence_Max(nextValue);
    int maxIncludingFirstValue = max(firstValue, maxNotIncludingFirstValue);    
    cout << "Leaving sequence_Max.  Returning " << maxIncludingFirstValue << endl;
    return maxIncludingFirstValue;
}

Enter a number like 8 (some value that is close to the end of a Hailstone Sequence). Brace yourself. Seeing recursion printouts can be mind-boggling when it's new. Line returns removed.

Entering sequenceMax -- n = 8
sequence_Max: Base case NOT met -- n = 8
firstValue = 8 nextValue = 4
Entering sequenceMax -- n = 4
sequence_Max: Base case NOT met -- n = 4
firstValue = 4 nextValue = 2
Entering sequenceMax -- n = 2
sequence_Max: Base case NOT met -- n = 2
firstValue = 2 nextValue = 1
Entering sequenceMax -- n = 1
sequence_Max: base case met. Leaving sequence_Max. Returning 1
Leaving sequence_Max. Returning 2
Leaving sequence_Max. Returning 4
Leaving sequence_Max. Returning 8

Now add the following line right before the return statement.

 cout << "(maxIncludingFirstValue, maxNotIncludingFirstValue) --> " << maxIncludingFirstValue << "\t" << maxNotIncludingFirstValue << endl;

Run it again with 4, 8, 16, and other values. If your mind wasn't blown before, it will be now. :) :)

Don't get too intimidated by this. It will make sense more later. But you'll see a pattern in the printouts. The point is that these printouts are not possible when the function is two lines like James had it. Again, James' function is the correct one and when you are done debugging things, take the cout/cin statements out and go to James' two-liner. But I think you'll find that a few printouts here and there will quickly solve many of your problems. For example, stick this at the top of your earlier function...

cout << "Entering sequence_Max -- n = " << n << endl;
cin.get(); // pause.  Hit Enter.

Note that if you enter 9 for n, you'll get a printout of 28 over and over again. It will never end. Whenever you see a recursive function call with the same n over and over again, something is wrong. The parameters should be changing. The problem is here...

int result = max(low, high);

But you'll never spot it due to the poor variable names. A quick change of variable names and the problem will (hopefully) jump out at you...

int firstElement = n, nextElement = next(n);
if (n <= 1)
{
    return 1;
}

//Base case.
else if (n != 1)
{
    int greaterOfFirstTwoElements = max(firstElement, nextElement);
    return sequence_Max(greaterOfFirstTwoElements);
}

Compare this to the algorithm and it's instantly clear that the code does not match the words. However, high, low, and result aren't precise enough to have it jump out at you.

0

I just picked a random number to start off with.

Ah. There's your problem. Don't make it random. Start with the base case. Make sure that works. Then try the second shortest Hailstone Sequence (2). Then the third shortest (4). Very often the bug will jump out at you very quickly with the trivial cases, whereas if you start with some random number it takes a while before to figure out what's up.

Note this post and the last post are generic posts regarding the overall process as opposed to geared towards your specific problem.

Can't agree more on the pencil/paper approach too, ESPECIALLY with recursion. Pencil and paper to figure out what SHOULD be going on, then add some cout statements to mak sure that is actually what is going on.

0

When I posted the "two line" version I was just trying to show the logic in pseudo-code, it just happened that's it's pretty close to actual code, depending on your language.
AssertNull is right (as usual) in that an experienced programmer would probably code it that way as well, but a learner would do far better to break it down and make the intermediate results visible for debugging. He's also right about variable names.

ps I keep referring to AssertNull as "he" in the absense of any biographical details. If that's not appropriate then I apologise to him/her/hir/whatever.

0

.........................blowing my mind is right. Knocked out my philosophy exam yesterday, 44 out of 50. Was stressing a bit over it all day yesterday. I emailed my professor and apparently there a two functions left from my original program I need to modify.

The one I'm currently working on is the int initialcomp_Num(int n) function. I'll place what my original functioned looked like with loops:

int initialcomp_Num(int n)
{
    //Variable Declaration.
    int count, initial, topValue, cal;

    //Function will work as intended if 'n' is not less than 1.
    if (n <= 1)
    {
        return n;
    }
    initial = sequence_Length(n);
    topValue = n;
    for (count = 1; count != n; count++)
    {
        cal = sequence_Length(count);

        if (initial <= cal)
        {

            topValue = count;
        }
        else if (initial >= cal)
        {
            topValue = topValue;
        }
    }
    return topValue;

I'll provide a background on my thought process (round 2) on what I believe I need to do:

Facts

  1. Base case - n <= 1
  2. I want the return to be the starting value of the longest sequence from 1 to n.

Draft plan

  1. I want to return the starting number of the longest hailstone sequence out of 1 to n range. Example (1 till 8)
  • To do this, I have no choice but to use recursion, thus i believe the following method is needed
    -- There are two functions that can be used with this program that were created previously: int next(int n) and sequence_Length(int n).
    -- I know I can use n's length and compare the lenght with 1 to n-1.

**Question***
Is there a way to compare length of n with length of 1, then 2, then so on within lets say
max(sequenceLength(n), sequence length( 1, 2, 3...n -1)
ruturn the starting value of the max? Would this still be considered recursion? Or returne initalcomp_Num(n)?

0

Well with the factorial, I just keep ruturning 0. I decided to change my base line to 'steps'.

int initialcomp_Num(int n)
{
    //Variable Declaration.
    int m = n-1, steps = n;

    //Guard. 
    if (n <= 1)
    {
        return 1;
    }

        //Base case. 
        if (steps > 1)
        {
            steps--; 
        }
            if (sequence_Length(n) > sequence_Length(m))
            {
                return initialcomp_Num(n);
            }

            else if (sequence_Length(n) < sequence_Length(m))
            {
                return initialcomp_Num(m);
            }

}

I keep running into the issue of keeping the camparsion starting value that has the hightest length, texting it, and did still returning it. Since I'm unable to change the variable's value, once it's been declared.

0

Put the recursion on the back burner temporarily. You have problems with your non-recursive function. It may or may not give the right answer, but it's doing some strange things. I can't figure out what you are TRYING to do with the non-recursive function, so I can't offer advice on how to turn it into a recursive function. I will again point out the problem with the variable names. They do not help me understand what you are trying to do...

int initialcomp_Num(int n)
{
    //Variable Declaration.
    int count, initial, topValue, cal;

    //Function will work as intended if 'n' is not less than 1.
    if (n <= 1)
    {
        return n;
    }
    initial = sequence_Length(n);
    topValue = n;
    for (count = 1; count != n; count++)
    {
        cal = sequence_Length(count);

        if (initial <= cal)
        {
            topValue = count;
        }
        else if (initial >= cal)
        {
            topValue = topValue;
        }
    }
    return topValue;
}

Line 23 does nothing, which means that lines 21 to 24 do nothing. Line 23 assigns topValue to equal itself, which is pointless.

So your code is now this...

int initialcomp_Num(int n)
{
    //Variable Declaration.
    int count, initial, topValue, cal;

    //Function will work as intended if 'n' is not less than 1.
    if (n <= 1)
    {
        return n;
    }
    initial = sequence_Length(n);
    topValue = n;
    for (count = 1; count != n; count++)
    {
        cal = sequence_Length(count);

        if (initial <= cal)
        {
            topValue = count;
        }
    }
    return topValue;
}

No clue what cal represents name-wise. initial and topValue make sense on lines 11 and 12 to initialize the longest sequence to the one starting with n outside of the loop. I'm thinking of how I would construct a loop to calculate a maximum and I know that I would not compare anything to the INITIAL value every trip through the loop. I would compare it to the MAXIMUM value. I also don't like count as a variable name for iterating through a loop. I like counter. So all in all, it's veryt hard to follow your code. Let's try this and see if you agree it is easier for you to follow.

int initialcomp_Num(int n)
{
    //Variable Declaration.
    int counter, length, maxLength, maxLengthStartValue;

    //Function will work as intended if 'n' is not less than 1.
    if (n <= 1)
    {
        return n;
    }
    maxLength = sequence_Length(n);
    maxLengthStartValue = n;
    for (counter = 1; counter != n; counter++)
    {
        length = sequence_Length(counter);

        if (maxLength <= length)
        {
            maxLength = length;
            maxLengthStartValue = counter;
        }
    }
    return maxLengthStartValue;
}

The logic is simple. First assign the longest sequence as starting with n. Then go through each value less than n can compare it to the max. If and when there is a new max, change it. Not sure whether your function worked or not for all values, but this one should. I kept your line 17 as it was as far as using <= instead of <. Not sure if it will ever be equal, but something to think about. If there's a tie for the longest sequence should you return?

I'll end this post here and look at your other questions. Overall point is before CONVERTING to recursion, make sure your original function makes sense.

And where did the factorial problem come from? Is that part of the Hailstone Sequence project or unrelated?

1

Cast your mind back a day or so when you were making great progress by starting with a short pseudo-code text description of the process and some pencil and paper simulation to check it out. You seem to have forgotten about that and are hacking code that frankly makes no sense.
Please do not write a single line more code until you have a working paper simulation.

Votes + Comments
Paper and pencil rarely fails.
0

Okay, very slight change to the code to make it easy to convert to recursion. The key here is that we want to figure out the maximum length and corresponding start value of everything LESS THAN n (i.e. up to n - 1) and compare it to the length of the sequence starting with n. Return the starting value of whichever is greater.

int initialcomp_Num(int n)
{
    //Variable Declaration.
    int counter, length, lengthn, maxLength, maxLengthStartValue;

    //Function will work as intended if 'n' is not less than 1.
    if (n <= 1)
    {
        return 1;
    }
    maxLengthStartValue = 1; // base case for n = 1
    maxLength           = 1; // base case for n = 1

    for (counter = 1; counter != n; counter++)
    {
        length = sequence_Length(counter);

        if (maxLength <= length)
        {
            maxLength = length;
            maxLengthStartValue = counter;
        }
    }

    // maxLength now contains the length of the longest sequence with a starting value up to n - 1.
    // maxLengthStartValue now contains the starting value of the longest sequence with a starting value up to n - 1.

    lengthn = sequence_Length(n);  // lengthn contains the length of the sequence starting with n

    // compare the the two lengths.  Return the starting value of the longer sequence.
    if(maxLength > lengthn)
        return maxLengthStartValue; // the longest sequence DOES NOT start with n.
    else
        return n; // the longest sequence starts with n.
}

Now convert this code from a loop to a recursive function. Not sure what you were trying to do before, but I think it's the wrong approach. I'm going to PM you the recursive function and you'll see how easy it converts. As before, don't look at it till you've struggled with it on your own for a while, but then if you're stuck, give it a try. I'll post it on this thread tomorrow, or you can when you decide to take a look at it.

0

I was using pencil and paper. I translated what I wrote down to this post. I then used hand simulation afterwards to see if it would work through recursion. The only reason I see that I'm not getting the result needed from that function is if the variable 'steps' isn't carrying over, because that is my base line that the recursion is working towards. I'm trying here, and what I come up with makes sense to me. Yes, if there are certain concepts that I'm unaware of or missing, I understand that what I provide doesn't add up to you all. I'm doing what I can with the information my professor provides and this schedule. I don't believe programming is something can be learned in its entirety in such a short timeframe.

I'm at least trying to work on the issue on my own at first, and then come forward with a question if I feel I'm just missing something. An extra pair of eyes can potentially help highlight errors that may not be obvious to someone.

I tried to provide a background on what the function is suppose to do.

But overall, I appreciate you all's help so far.

v/r

Edited by Sherwin_4

0
int initialcomp_Num(int n)
{
    //Variable Declaration.
    int m = n-1, steps = n;

    //Guard. 
    if (n <= 1)
    {
        return 1;
    }

    //Base case. 
    if (steps > 1)
    {
        steps--; 
    }
    if (sequence_Length(n) > sequence_Length(m))
    {
        return initialcomp_Num(n);
    }

    else if (sequence_Length(n) < sequence_Length(m))
    {
        return initialcomp_Num(m);
    }
}

You can get rid of the "guard". You should design your base case to "guard" against any value you need to guard against. Your base case should be the value of n where no recursive call is needed. In other words, when n is 1. If you want to protect against n being LESS than 1, you can have that be the base case. You can call it a guard or you can call it a base case, but there's no reason to have a guard AND a base case. If you find yourself needing both, you probably have a design flaw.

// Base case
if(n <= 1)
    return 1;

That goes at the top before any potential recursive calls. You can declare the variables above that or below that. It really doesn't matter, so since you have them above, keep them there. If you want to have a variable called m and define it as n-1, that's fine. As for steps, it doesn't do anything. You already have n as the parameter. In your example, n is 8. You'll call the function recursively with n = 8-1 = 7. Then n = 7-1 = 6. Then n = 6-1 =5. Then n = 4,3,2, and finally 1. When n is 1, your base case is hit and it stops calling itself.

Having the variable m defined as n-1 is harmless, but having a variable called "steps" and having it "carry over" tells me that you have a fundamental misunderstanding of how recursion works. You should have ONE variable that "carries over" and steadily decreases till it hits the base case, and that is the function parameter, which is n. Stick a cout statement at the top of the function to display n if that helps you see what is happening (see my earlier posts on how to do that as part of the debugging process. Remember to take it out when you're done). n should be steadily counting down from 8 to 1, then stop. If it isn't doing that, you've found a problem. Note that I realize that you are not allowed to change n inside the function. This may sound contradictory, but it isn't, and understanding that is the basis of understanding recursion. n will not change WITHIN the function, but if the original n is 8, then you want to have eight function calls, each with a different value of n, and each successive call should get closer to the base case. You do not need to change n in the function to accomplish that and you do not need a separate variable called steps or anything else to accomplish that.

The main problem is here. You have infinite recursion, or at least you potentially do.

return initialcomp_Num(n);

Since n has not changed, you're calling your function here with 8 again. And again. And again. And again and again till you eventually call the function millions of times, all with a value of n=8 intead of 8 function calls total, and you'll eventually run out of memory. Calling the function with m is fine since m is n-1.

It takes a while to get it. You're right on that one. It's good that you're trying to get it on your own. That's why I PM'd you a solution rather than posting it here. Play around with the steps idea. Nothing wrong with that. You'll either get it to work or you'll play with it long enough without it working to decide it's not going to work. Either way you'll likely learn something through the experimentation.

I think if you truly go through detailed step-by-step and get the pencil and paper perfect, you'll then go through your code and see somewhere where the code does not follow the pencil and paper approach. If you get too frustrated, look at the PM I sent you and see if that makes sense to you. Change as desired so it works for YOU (Who cares if it makes sense to me. I've already graduated. It DOES, of course, have to make sense to your professor and any graders :) ). And name your variables in a way that makes sense to YOU. To the extent that renaming them helps clarify what the code is doing, rename them. If renaming them hinders your thought process, don't. Personally, I comment and name my variables more so that I can follow my OWN code as much as I do for anyone else.

I won't bring up the variable naming again. My philosophy, in general, is that if you can't articulate your thinking process to another person (ie me), you won't be able to articulate it to the computer, which has no common sense at all. I used to drive my students mad by being intentionally obtuse and making them explain every single detail of what they were trying to do. A bunch of them thought I was messing with their heads and being a jerk, but (at least I felt) there was a method to my madness. In the end, if you can speak very precisely in English, it will translate to C++ well and your mind will be in the right place for coding. Thus forget about whether you can explain the "steps" variable to ME. Instead, clone yourself and explain the "steps" variable to your clone. Then pretend you're the clone who knows absolutely nothing about the project except for your explanation. You're on the right track if it makes sense to the clone and if neither of you are getting frustrated with each other.

Good luck. Recursion is bizarre at first, but it'll eventually click. Very often it clicks AFTER the final exam and AFTER the assignments have all been graded.

Edited by AssertNull

1

You can call it a guard or you can call it a base case, but there's no reason to have a guard AND a base case. If you find yourself needing both, you probably have a design flaw.

I respectfully disagree.
A guard protects the following code from incorrect or invalid values
A recursion base case is the case where recursion stops
They are two different things with different uses, and shouldn't be confused. eg

int next(int n) {
    if (n<1) raise error "algorith is undefined for n<1"  // guard
    if (n = 1) return 1;  // base case
    ...

I don't know about C++, but Java uses assert for guards (can be turned on or off at runtime for improved error checking vs performance), and Swift has explicit guard statements/

Personally I'm huge fan of guards to document and enforce a method's pre-conditions

Edited by JamesCherrill

Votes + Comments
Good food for thought.
0

You make a good point. Programmers must list their assumptions regarding good data and must decide whether/how to handle it. I imagine the general Java approach would be to handle just about all bad data and either abort with a useful error message or give an option to correct the better data. The C/C++ philosophy is generally to give the programmer the TOOLS to do these things, but not necessarily require it. Thus assert does exist in C++. If you decide not to handle it, it's generally considered nice to at least leave a comment saying "A non-positive value for n results in undefined behavior". Your favorite term.

Way back in these Hailstone threads, I set up a guard in main making sure than n would be positive before the function was called. Hence no guards needed in the actual function since it was handled before. One can make a decent argument that having a redundant guard in the functions itself is the way to go. What's the harm?

A guard guards against something that when all goes well, will never be needed, whereas the BASE CASE, by design, WILL be used and the function won't work without it, so different concepts and I can see why one might code to make that distinction clear to the reader. In this particular case however, the OP had been blending the two (n <= 0: guard and n== 1: base case) all along into one line in the pre-recursion functions, so why not continue with that approach?

// guard
if(n <= 0)
    return 1;

// base case
if(n == 1)
    return 1;

Combines into one line...

if(n <= 1)
    return 1;

But again, you do bring up a valid point. There might be value in having the two separate. In that case, good comments are essential, and be consistent.

On a separate matter, you have a slight bug in your case or it may have been pseudocode. I knew what you meant, but since the OP is a newbie, a simple copy/paste not realizing it could cause endless headaches, so I'll point it out...

if (n = 1) return 1;  // base case

This is the dreaded = versus == bug. It's so incredibly easy to do. We've all done it and the compiler generally doesn't pick up on it (some throw out a helpful hint of the possibility if you use the right compiler flags) since it is not a bug. It is legitimate code and your eyes very often will not catch it. Experienced programmers know to look out for it, but for a newbie who doesn't know to look out for it, it ranks up there as one of the most frustrating things there is and you'll spend all your time looking at everything BUT that and debugging other areas of the code that have no bugs.

What it does is ASSIGN n to equal 1, then return 1, rather than do a base case comparison. You'll never get past that line. You want this...

if(n == 1) return 1; // ==, not =

Interestingly enough, the OP is not allowed to change n due to his spec. I assume that the OP has not learned about the const qualifier yet, which WOULD cause the compiler to flag this bug regardless of compiler flags.

int initialcomp_Num(const int n)
{
    if(n = 1) return 1; // base case with bug

    // recursion code below
}

The above will cause the compiler to point out the error. ANOTHER way to avoid the error is to code like this...

if(1 == n) return 1;

as opposed to the more trraditional way...

if(n == 1) return 1;

The compiler will catch the first one if = is written instead of == accidentally, but not the second one. You can add this compiler flag, though...

-Wparentheses

and look for this warning: suggest parentheses around assignment used as truth value

theconst qualifier and adding compiler flags may be beyond the OP's skill level at the moment. If so, your professor will get to it in good time, so don't divert from the syllabus to learn this stuff if it distracts from your goal. Just throwing it out there as something to be aware of.

1

Last post from me in this thread. I won't have time to log into Daniweb for at least a week, so I am posting the code that I sent Sherwin via PM below before I forget. Sherwin, if you don't want to see the code yet, stop reading this post. For anyone else who may be interested, here it is...

int initialcomp_Num(int n)
{
    //Variable Declaration.
    int lengthn, maxLength, maxLengthStartValue;

    //Function will work as intended if 'n' is not less than 1.
    if (n <= 1)
    {
        return 1;
    }

    maxLengthStartValue = initialcomp_Num(n-1);
    maxLength = sequence_Length(maxLengthStartValue);
    // maxLength now contains the length of the longest sequence with a starting value up to n - 1.
    // maxLengthStartValue now contains the starting value of the longest sequence with a starting value up to n - 1.
    lengthn = sequence_Length(n);  // lengthn contains the length of the sequence starting with n

    // compare the the two lengths.  Return the starting value of the longer sequence.
    if(maxLength > lengthn)
        return maxLengthStartValue; // the longest sequence DOES NOT start with n.
    else
        return n; // the longest sequence starts with n.
}
1

if (n = 1) return 1;

No, not a bug, because yes, that's pseudo-code. Depending on you language you may have to code the test for equality differently (but not, for example in SmallTalk or Pascal). The whole discussion of = vs == in C derivatives is, of course, correct, but not really what this is about.

This recursive algorithm is interesting because you really want to return both the index n of the longest sequence and its length. In (most?) C-like languages you can't easily do that, so you have to return n, and then you need a duplicated call to sequence_Length (line 13) While looking at this myself I was tempted to define a class or struct with both n and its corresponding sequence length just so I could return that but it did seem overkill. If I were to become worried about the efficiency issue of duplicated calls to sequence_Length I would probably prefer to use a Map to cache known n,sequenceLength pairs and thus eliminate re-calculations.
Swift allows you to return an arbitrary tuple from a method, which seems to me to be the cleanest way to code this. (You may be getting a suspicion that Swift as is my favourite language, successfully incorporating the lessons of Java, C* etc , and you would be right.)

Edited by JamesCherrill

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.