Recursion program

[Shannon Holder]

Hello, All! I am trying to make this program work and have hit a dead end. The assignment is to write two recursion functions: one that takes a string and reverses it and another that finds the maximum value integer in an array. I have written the program and am not getting any errors, or warnings, but the program does not run. Just gives me a blank screen. The problem seems to be in my array declaration because if I place any statement before that, it runs. I realize this is a simple program and my mistakes are going to be rookie mistakes, but, hey... I AM a rookie. Can anyone help me see my error here?
Due tomorrow!

HERE IT IS:

#include <iostream>
#include <cstdlib>
#include <string>

using namespace std;

//function prototypes
void reverseDisplay(const string &s); 
int largest(int *list, int highest_index);	
void reverseDisplay(const string &s, int high);

int main()
{
 cout << "test run" << endl;
	//Test Largest function
    const int SIZE = 10;
	int listOfInts[SIZE] = {1,2,5,7,3,4,9,0,6};	 //an array of integers
cout << "\n\nThe largest integer in the list is " << largest(listOfInts, 9) << endl;	
	
	//Test function reverseDisplay
	cout << "Please enter a string... " << endl;
	string sreverse;
	getline(cin, sreverse);  //asks user for a string

	reverseDisplay(sreverse);  //sends string to function for reversing

	system ("pause");
	return 0;
}

//FUNCION DEFINITIONS

//function that returns the largest integer in an array 
int largest(int *list, int highest_index)	
{
	static int max;	
	
	for(int i = 0;i != highest_index ;)
	{
	      if(list[i] > list[highest_index])
		{
			max = list[i];
			largest(list, highest_index -1);
		}
	      else if(list[i] < list[highest_index])
		{
			max = list[highest_index];	
			i++;
		}
		
	}
	return max;
}

//function that reverses the order of a string

void reverseDisplay(const string &s, int high)	//helper reverse function
{
	//create a new string to take the reverse of string s
	string s2;		

	//loop to assign reversed values to s2
	for(int i = 0, j = high; ; i++)
	{
			
	    if(i == high)
	        cout << "The string reversed is " << s2 << " ."; 
			
	//reverse order of s and assign it to j
	    else  
	    {
		s2[j] = s[i];
		reverseDisplay(s, high -1);
	    }
	}
}

void reverseDisplay(const string &s)  //reverse display function
{
	reverseDisplay(s, s.size() - 1);
}

[Zephilinox]

please use [code][/code] tags

[binarybob350]

What is the definition of recursion, see recursion.

[Shannon Holder]

To answer your question: recursion is repeatedly applying a function to itself. I cannot, however, tell if I have written the recursion functions correctly because, it appears, that there is an error in my main function??? It will not run past the first line of main().

[Lowest0ne]

Your array is of size 9, which means the highest index is 8.

I believe you can also remove the [9] when you declare the array, just have it be

int listOfInts[] = {1,2,3,4,5,6,7,8,9};.

[Shannon Holder]

Thank you, LowestOne, I fixed this but the program still does not run, and still no errors are reported. Notice that I added "test run" to the beginning of main, this runs just fine, it still appears that the program fails at the array.

[Shinigami]

int largest(int *list, int highest_index);
here you use pointer, but you give to it array. My compiler gives errors then I try to do it.
So I use this.

int largest(int [], int);

And you don't need to write variable names in prototypes, but you can do it.

Line 43 to are wrong. You function returns int, but don't have variable to give it to.

And reverseDisplay never will return any value as variable s2 at if(i == high) don't have a value.

and (again) for(int i = 0, j = high; ; i++) will never stop. As you increase value of variable i, but are comparing to variable j

[Shannon Holder]

Thank you, Shinigami, my professor actually gave us the specified function headers so I have to use the pointer. I thought that this was a proper way to use pointers as arrays??? But, I am pretty green, I did try changing the function headers to take the less "elegant" version of an array (this is what my prof calls it :-) ) and the program still did not run.

[Shannon Holder]

Again, the functions are NEVER called. The program fails in the first lines of main(), before the functions have a chance to be called. Even if my functions are not written correctly, this not where the program is failing.

[Shinigami]

Your program runs, but it never stops in line 18. As function largest() never ends.

[Shinigami]

Try this and you will see.

int largest(int list[], int highest_index)	
{
	static int max;	
	
	for(int i = 0;i != highest_index ;)
	{
	      if(list[i] > list[highest_index])
		{
			max = list[i];
			cout << "First: " << max << endl;
			largest(list, highest_index -1);
		}
	      else if(list[i] < list[highest_index])
		{
			max = list[highest_index];
			cout << "Second: " << max << endl;	
			i++;
		}
		
	}
	return max;
}

[Disch]

You're chasing a red herring. This has nothing to do with main or your array.

The problem is your largest function never exits and it is deadlocking your program.

In 'largest': if(list[i] > list[highest_index]) in that block you do not increment i, which means each time the loop runs it will keep entering that block over and over and will never advance.


A better way to debug these kinds of problems is to actually use a debugger (set breakpoints), rather than log some statements to cout. Logs are open to interpretation and can be deceptive, but breakpoints never lie.

[Shinigami]

he increase i in line 48, but here still are problems in function.

[Shannon Holder]

Thank you, Everyone!

I did try your code, Shinigami and I got the correct output but it is returning an infinite loop.

Disch, I didn't incriment I but I did decrement highest_index... the idea was to compare the first index to the last and if the first is the lowest, to incriment it while leaving highest_index and comparing it to i++. Else if the last index is the lowest to decrement highest_index and comparing the next index down to i.

I don't know about breakpoints and I am using DevC++ to compile...

[Shannon Holder]

Okay, Shinigami... you were trying to show me that my loop was infinite... hmmm...

[Shinigami]

yes I know, I only show you that you program runs in infinite loop. And if you use recursive function you don't need for(); As recursion is going over array.

[Disch]

Nowhere in the code you posted are you modifying i or highest_index:

int largest(int list[], int highest_index)	
{
  //...static int max;	

  for(int i = 0;i != highest_index ;) // loop depends on either 'i' or 'highest_index' changing
  {
    if(list[i] > list[highest_index])
    {
      max = list[i]; // <- not changing either of them
      cout << "First: " << max << endl;
      largest(list, highest_index -1);  // <- not changing either of them
    }
    //... 

This = deadlock.

You are passing highest_index - 1 to a separate call of largest, but that does not change the value of highest_index in the current call of largest. So when the separate call returns, the original call will just call it again with the exact same params.... and again... and again.

[Shinigami]

this works

int largest(int list[], int highest_index)	
{
	int min = 0, max = list[highest_index];
	if (highest_index)
		min = largest(list, highest_index - 1);
	if (max < min)
		max = min;
	return max;
}

don't know if it is best way, but it works.

[Shinigami]

and you need only one reverseDisplay(string s) function. And here can be 3 lines in it.

[Shinigami]

this is better

int largest(int list[], int highest_index)	
{
	int min = list[0], max = list[highest_index];
	if (highest_index - 1)
		min = largest(list, highest_index - 1);
	if (max < min)
		max = min;
	return max;
}