ken6208 ken6208 - 2 months ago 6
C++ Question

C++ | Need Help Transitioning From A For Loop Function -> a Recursive Function

So for one of my homework assignments we were asked to create a hailstonesequence and I'm completely stuck. I have a hard time figuring out how to break down segments of a function containing loops, and then trying to essentially translate it into a recursive function. Any help would be greatly appreciated. Down below I have the original for-loop function, and then the (Attempted) recursive function.

// startingValue function with For-Loop
// Takes in an int value n and returns the
// start value k from 1 to n, that has the longest length.

int startingValue (int n) {
int length = 0;
int k;

for ( int i = 1; i <= n; i++ ) {
int currentLength = largestHailstoneLength(i);

if (currentLength > length) {
length = currentLength;
k = i;
}
}

return k;
}


Here's my attempt for a recursive version of the function above:

int startingValue (int n) {
int length = 0;
int n = 0;
int currentLength = largestHailstoneLength(i);

if (currentLength < length) {
return 0;
} else {
length = currentLength;
n = i;
}

return (startingValue(i));
}

Answer

There are a few problems in your code

  1. You don't define i inside your recursive function
  2. You don't seem to have a clue on how recursion works, I'll give you a clue:
    • Each time you call a function, you save a state.
    • You need to state where your recursive function stops, or it will keep calling itself until it crashes with stack overflow.
    • You need to know whether you wan't to work with what is returned by the function or if you want to work with what you're passing to it (or both)

If I got it right, startingValue() should return a value to which largestHailstoneLength() is the greatest possible.

So what we follow here is an induction principle:

  • I have n values
  • If n is 1, i don't have to run any comparisons, just return n.

Otherwise

  • If n is the greatest, it should be greater than the greatest between 1 and n - 1.
  • Now we need to see the greatest between 1 and n - 1.
  • If n - 1 is the greatest, it should be greater than the greatest between 1 and n - 2
  • ...

Well then, the fisrt thing to do is check for n

// Stop here, no need to go compare
if (n == 1) return n;

What we need to do inside the recursion is to compare the current n with the greatest from 1 to n - 1. that is:

// If current n is greater then the best case for n - 1
int k = startingValue(n - 1);
if (largestHailstoneLength(n) > largestHailstoneLength(k))
{
    // n is greater
}
else // startingValue(n - 1) is greater

Knowing which is the greater one, we simply return it.

To understand things better, read a little bit more. You can begin here.

Comments