Don't know how to do a recursive call

[Nillen]

Hey, I'm not sure what I'm supposed to do. I know that a recursive call is a function that calls itself, by passing a number to itself that it then uses for another run. But I don't know how I should apply that to my assignment.

My assignment, the only part left, is to search for an age within a class of students. My function needs to use a binary search algorithm and it needs to be recursive. But I'm clueless as to how I should do it.
Here's the full code of what I've done.

I'm calling the binary search at line 152, and the actual function is at line 40

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

class Student //Class
{
public: //Main can access

	string name;
	int age;

	void print() //Print them
	{
		cout << "Student: " << name << endl;
		cout << "Age: " << age << endl;
	}

	void store(string _name, int _age) //Store them
	{
		name = _name;
		age = _age;
	}


};

int LinearSearch(Student* studentArray, int age, int students) //Linear Search Function
{
	for (int i = 0; i <= students; i++) //Loop through ages of students
	{
		if (studentArray[i].age == age) //If age of student == Input age
		{
			return i; //Return Student ID
		}
	}
	return -1; //Outside loop, didn't return a value, so return -1
}

int BinarySearch(Student* studentArray, int age, int min, int max) //Binary Search Function
{
	Student student[5];

	int s;
	int search;
	s = (max - min) / 2;
	search = studentArray[s].age;
	if (age == search) 
	{
		return search;
	}
	else if (age < search)
	{
		BinarySearch(student, age, min, s);
	}
	else if (age > search)
	{
		BinarySearch(student, age, s, max);
	}
	else if (search == max)
	{
		return -1;
	}
}

bool sort(const Student& lhs, const Student& rhs) //Sort Function
{
	return lhs.age < rhs.age; //Return lowest values
}


int main()
{

	Student student[5]; //Create 5 slots for Student Class
	string name;
	string teacher;
	int age;

	int students;
	students = 4;

	cout << "Welcome, what's your name?: ";
	cin >> teacher;
	cout << "Welcome to your new job, " << teacher << ".\n\n";

	cin.get();
	cout << "As a new teacher, you will have to set up your class in this program.";
	cin.get();
	cout << "Note that you're only allowed to teach 5 students as max.";
	cin.get();
	cout << "Please enter your students' information below\n";

	for (int i = 0; i <= students; i++) //Loop through amount of students inputted
	{
		cout << "Enter student " << i << " name: ";
		cin >> name;
		cout << "Enter student " << i << " age: ";
		cin >> age;

		student[i].store(name, age); //Store all students information
	}
	
	cout << "Let's make sure your students got put in correctly.\n";
	cout << "Print student ID: ";

	int input;

	while (true)
	{
		cin >> input;
		if (input <= students)
		{
			student[input].print(); //Print student information
			break;
		}
		else
		{
			cout << "Error, student " << input << " does not exist. Please try again: ";
		}
	}

	cout << "\nTime skips until after spring break...\n";
	cin.get();
	cout << "Welcome back, " << teacher << ".";
	cin.get();
	while (true)
	{ //Infinite while opening bracket
		cout << "\nWhat activity do you want to do today?\n";
		cout << "1. Search information about a student (Linear)\n";
		cout << "2. Search information about a student (Binary)\n";
		cout << "3. Print class in order of age\n";
		cout << "4. Quit\n";

		cin >> input;
		if (input == 1) //Linear Search
		{
			int search;
			cout << "Student age: ";
			cin >> age; 
			search = LinearSearch(student, age, students);
			if (search == -1) //Returned not found
			{
				cout << "Error: There's no student by the age: " << age << endl;
			}
			else //Returned found
			{
				cout << "The first match was: " << student[search].name << endl;
				cout << student[search].name << " is student number: " << search;
			}
		}
		else if (input == 2) //Binary Search
		{
			sort(student, student + students, sort); //Uses <algorithm>
			int search;
			cout << "Student age: ";
			cin >> age;

			search = BinarySearch(student, age, 0, students); 
			if (search == -1)
			{
				cout << "Couldn't find student by age: " << age << endl;
			}
			else
			{
				cout << "Student ID: " << search << endl;
				student[search].print();
			}
		}
		else if (input == 3) //Sort
		{
			sort(student, student + students, sort); //Uses <algorithm>
			for (int i = 0; i <= students; i++)
			{
				student[i].print(); //Print student info
			}
		}

		else if (input == 4) //Quit
		{
			exit (EXIT_SUCCESS); //Only way to exit infinite while
		}
		else if (input == 5)
		{
			for (int i = 0; i <= students; i++)
			{
				student[i].print(); //Print student info
			}
		}
	} //Infinite while closing bracket


	cin.sync();
	cin.get();
	return 0;
}

[LB]

AT the beginning of lines 54 and 58, you just need to add return

[Nillen]

Thanks LB, I did as you told, but I'm still getting an Error saying 'BinarySearch' : not all control paths return a value

I'm not sure how it translates into a value for the main() when I use a recursive calling in the function though, could that have something to do with it?

[LB]

Your compiler is stupid. Delete line 60 (it is redundant as that is the only possibility at that point in the code).

[zdzero]

Because not all your control paths return a value. Let's take it step by step.

int BinarySearch(Student* studentArray, int age, int min, int max) //Binary Search Function
{
        //    let's call this the main control path
	Student student[5];

	int s;
	int search;
	s = (max - min) / 2;
	search = studentArray[s].age;
	if (age == search)    //    this is the first branch in your code path
	{
		return search;    //    and it returns something - control path 1
	}
	else if (age < search)    //    this is another branch, but it returns nothing - still control path 0
	{
		BinarySearch(student, age, min, s);  
	}
	else if (age > search)    //    another branch, no return, still control path 0
	{
		BinarySearch(student, age, s, max);
	}
	else if (search == max)    //    new branch
	{
		return -1;    //    new return, control path 2
	}
        //    we are back on the control path 0, but no return
}

I hope that wasn't hard to understand.

Now, in order to make this function recursive it needs to call itself. It already does that (lines 54 and 58 in your first post).
But this isn't all. Your recursive function returns a value, and that value is computed from multiple iterations. This means that lines 54 and 58 should be

	return BinarySearch(student, age, min, s);  

and

	return BinarySearch(student, age, s, max);

When your code reaches one of those 2 ifs it means that it hasn't found the answer yet, but there are still places in which to look for it, so the task is passed to the next function call.

If you still have trouble understanding this I'll post an example.

[LB]

@zdzero: if x is not less than y and x is not greater than y, the only possibility is for x to be equal to y. All control paths return a value - the compiler just doesn't understand basic logic.

[Nillen]

So, what I did was remove the line suggested, and replace it with

else 
{
return -1;
}

And I'm not getting the error in my error list anymore. However, when I tried running it, it gave me this: http://i.gyazo.com/a7c62d40a49ee68435cd902ec7055a5d.png

This is after adding a student with the age 15, and searching for the age 15.
If it's relevant, I'm using the latest Microsoft Visual Studio

Sorry, the only other language I know is mSL (mIRC Scripting Language) so I might not have done it all correctly.

[zdzero]

In the form the function is now the compiler is right:
Right now the function returns for this cases:
- age was found in the array
- the end of the array was reached
What happens when age was not found but the end was not reached? Sure, you call BinarySearch again, but that BinarySearch will return to this BinarySearch and what will this Binary Search do?

For you, a human, it may look like every time there is something returned, but the compiler is right.

Let's make things even more clear:

	int tempResult = BinarySearch(student, age, min, s);  
        return tempResult

edit: oh, why can't I draw something?

CALL 0:
	Array: 0,1,2,3,4,5,6,7,8,9,10,11,12; Age: 4
	The element in the middle is 6
	6 > 4:
	the result of this call will be the one from the next
		CALL 1:
			Array: 0,1,2,3,4,5; Age: 4
			The element in the middle is 2
			2 < 4:
			the result from this call will be the one from the next
			CALL 2:
				Array: 3,4,5; Age: 4
				The element in the middle is 4
				4 == 4:
				return it's position (4) to the previous call (CALL 1)
			received a response from CALL 2, give it back to the previous call (CALL 0)
	received a response from CALL 1, give it back to main
	

[Nillen]

@zdzero Sorry, but you just melted my brain with that.

See post below!

[LB]

@zdzero: I think you are confused because Nillen did not post his latest code after he fixed it.

@Nillen: click Break and use the debugger to see what went wrong. You can also set a breakpoint on the previous line and run the program again so that the debugger starts before the crash instead of after.

[Nillen]

int BinarySearch(Student* studentArray, int age, int min, int max) //Binary Search Function
{
	Student student[5];
	
	int s;
	int search;
	int result;
	s = (max - min) / 2;
	search = studentArray[s].age;
	cout << "DEBUG: " << search << endl;
	if (age == search)
	{
		return search;
	}
	
	else if (age < search)
	{
		result = BinarySearch(student, age, min, s);
		return result;
	}
	else if (age > search)
	{
		result = BinarySearch(student, age, s, max);
		return result;
	}
	else
	{
		return -1;
	}
}

That's my function right now, after changing all the things you mentioned.
I did find an error in the code, when I added the DEBUG line I noticed that it only returned negative values similar to -885585

Did I mess up by creating class slots inside that function? How else do I call the already created class list?

[LB]

In your most recent code snippet: delete line 3 and use the first parameter of your function instead (studentArray).

[zdzero]

@zdzero: I think you are confused because Nillen did not post his latest code after he fixed it.

To be fair, I was talking about his original code. But I did it only to make some basic things more clear for him.
But the compiler was right with that warning, your solution was just as good as mine.

@zdzero Sorry, but you just melted my brain with that.

The main idea is that function calls "build" from one to the next, and the "return road" is the same as the "call road", there is no skipping.

Attacking the current problem, are you sure you're not going outside some boundaries? If your array has 6 entries (going from Array[0] to Array[5]), your initial call needs to set Min to 0 and Max to 5 (the 6th element is on index 5, so you don't want to touch index 6).

[LB]

The issue is that line 3 declares an array of uninitialized values and then the code uses that, instead of using the array passed to it.

[Nillen]

I assume you mean replace all instances of "s" with studentArray
But I was trying to set studentArray = (max - min) / 2;
and it gave me an error that a value of type "int" cannot be assigned to an entity of type "student *"

[zdzero]

He actually talks about this part

	else if (age < search)
	{
		BinarySearch(student, age, min, s);
	}
	else if (age > search)
	{
		BinarySearch(student, age, s, max);
	}

The first argument should be studentArray, not student.
You have a Student student[5]; declared that hold uninitialized data and you're sending that as a parameter by mistake.

[Nillen]

Thanks! That was exactly what I needed! You guys are life savers! =)

I'm not yet at the point at which I understand the whole code, but some day I will be =)

I simply switched out return search; to return s; so I can print the student's information using student[ID].print()

:D

[fg109]

I think this

	if (age == search)
	{
		return search;
	}
	
	else if (age < search)
	{
		result = BinarySearch(studentArray, age, min, s);
		return result;
	}
	else if (age > search)
	{
		result = BinarySearch(studentArray, age, s, max);
		return result;
	}
	else
	{
		return -1;
	}

should be changed to this

    if (age == search)
        return search;
    else if (min == max)
        return -1;
    else if (age < search)
        return BinarySearch(studentArray, age, min, s - 1);
    else
        return BinarySearch(studentArray, age, s + 1, max);

^Most important change is the placement of return -1;.

[LB]

@fg109: you have not changed the code at all other than to make it harder to read.

[fg109]

@LB

From what I can tell, the original code would have sent the program into an infinite recursive loop if the search target was not within the array. It would never have gotten to the return -1;

@Nillen

It should be s = (max + min) / 2;