-
September 22nd, 2010, 03:09 PM
#1
Need help regarding recursion
Hi to all,
Hope you all will be fine. Actually i am trying to make a very simple program that checks that how many times a desired number is coming in the array. I have made it using for loop. But when i came to recursion, then i am stuck at logic. Here is the code, i commented out the for logic. Actually when the base condition true then it returns only element at index0 always.
Code:
int _tmain(int argc, _TCHAR* argv[])
{
//Function prototype
int count(int numberToFind, int integerArray[], int length);
const int arraySize = 5;
int numberToFind;
int integerArray[arraySize];
cout << "Enter 5 integers each followed by <return>" << endl;
for (int i=0; i<arraySize; i++)
{
cin >> integerArray[i];
}
cout << "Enter number to find in array: ";
cin >> numberToFind;
count(numberToFind, integerArray, 5);
system("pause");
return 0;
}
int count(int numberToFind, int integerArray[], int length)
{
if (length == 0)
{
return integerArray[length ];
}
else
{
if (numberToFind == count( numberToFind, integerArray, length-1) )
{
cout << "Number Found " << endl;
}
}
/*for (int i=0; i<length; i++)
{
if (numberToFind == integerArray[i])
{
cout << "Number Found " << endl;
}
}*/
return 0;
}
what i am doing wrong?
Thanks
-
September 22nd, 2010, 03:13 PM
#2
Re: Need help regarding recursion
Code:
if (length == 0)
{
return integerArray[length ];
}
Red flag #1: arr[length] is never a valid index. If the length is 0, then there *are* no valid indexes. If the length is 1, then 0 is the only valid index, if it's 2 then only 0 and 1 are valid, etc.
Code:
if (numberToFind == count( numberToFind, integerArray, length-1) )
{
cout << "Number Found " << endl;
}
This if statement doesn't make a lot of sense. You're comparing a number you're looking for to a count. Shouldn't you be comparing it to some element of the array instead?
-
September 23rd, 2010, 02:36 PM
#3
Re: Need help regarding recursion
Code:
if (length == 0)
{
return integerArray[length ];
}
arr[length] is never a valid index. If the length is 0, then there *are* no valid indexes. If the length is 1, then 0 is the only valid index, if it's 2 then only 0 and 1 are valid, etc.
but here
Code:
integerArray[length ];
return first element in the array. I need to compare it like this
Code:
numberToFind == integerArray[0 ]
numberToFind == integerArray[1]
numberToFind == integerArray[2 ]
numberToFind == integerArray[3 ]
numberToFind == integerArray[4 ]
This time i tried this but this didn't work too
Code:
int count(int numberToFind, int integerArray[], int length)
{
if (length == 0)
{
return numberToFind;
}
else
{
return (integerArray[length-1] == count( numberToFind, integerArray, length-1) );
}
}
I am newbie, but I'll make it .
-
September 23rd, 2010, 02:45 PM
#4
Re: Need help regarding recursion
You seem to be getting confused about elements in the array versus counts. Perhaps it would be clearer if the elements in the array were not integers? The logic would be the same, but the compiler would be more capable of helping you out with compile errors when you do something wrong. Try this:
Code:
#include <string>
using std::string;
int count(string wordToFind, string stringArray[], int length)
{
if (length == 0)
{
return wordToFind;
}
else
{
return (stringArray[length-1] == count( wordToFind, stringArray, length-1) );
}
}
The compiler will throw all kinds of errors at you because it's currently wrong. Fix it like this first, and then change the type back to int.
-
September 23rd, 2010, 03:20 PM
#5
Re: Need help regarding recursion
it says
Code:
int count(string wordToFind, string stringArray[], int length)
{
if (length == 0)
{
return wordToFind; //error no suitable conversion from std::string to int
}
if i change return type to string
Code:
string count(string wordToFind, string stringArray[], int length)
{
else
{
return (stringArray[length-1] == count( wordToFind, stringArray, length-1) ); //error no suitable constructor exist to convert from "bool" to "std::basic_string<char, std::char_traits<char>,std::allocator<char>> "
}
}
first error is ok. It's easy to find that error is due to, return type is int and i am trying to return string but what about second error?
thanks
-
September 26th, 2010, 12:31 PM
#6
Re: Need help regarding recursion
This code is working fine
Code:
.........
.........
int number = count(numberToFind, integerArray,/*length of integerArray */ sizeof(integerArray)/sizeof(int));
cout << "number: " << number << endl;
system("pause");
return 0;
}
int count(int numberToFind, int integerArray[], int length)
{
if (length < 0)
{
return (0);
}
if(integerArray[length] == numberToFind)
{
return (1 + count(numberToFind, integerArray, length-1));
}
else
{
return count(numberToFind, integerArray, length-1);
}
}
-
September 26th, 2010, 09:52 PM
#7
Re: Need help regarding recursion
Originally Posted by Basit781
This code is working fine
No, it is not. Here, an explanation:
Code:
#include <iostream>
int count(int numberToFind, int integerArray[], int length) {
if (length < 0) {
return 0;
}
if (integerArray[length] == numberToFind) { // integerArray[10]?!
// when calling the function we specified that the array is
// 10 elements long, so integerArray[10] is buffer overflow!
// (it's not actually in this case though, cause we defined 11-element
// array - so this would be "emulated" buffer overflow)
// This shows clearly, that the function was not reliable, and could
// actually return wrong value at some point, because of buf.overfl. error
return (1 + count(numberToFind, integerArray, length - 1));
} else {
return count(numberToFind, integerArray, length - 1);
}
}
int countFixed(int numberToFind, int integerArray[], int length) {
if (length < 0) {
return 0;
}
--length; // no buffer overflow now
if (integerArray[length] == numberToFind) {
return (1 + count(numberToFind, integerArray, length));
} else {
return count(numberToFind, integerArray, length);
}
}
int main() {
int arr[11];
arr[0] = 1; arr[1] = 2; arr[2] = 3; arr[3] = 1; arr[4] = 2;
arr[5] = 1; arr[6] = 2; arr[7] = 2; arr[8] = 4; arr[9] = 1;
arr[10] = 1; // 11th element, which will "emulate" memory space "after" our
// 10 element array
int number = count(1, arr, 10); // should return 4, since only 4 ones are in
// elements indexed from 0 to 9
std::cout << "number: " << number << "\n"; // prints "number: 5"! A-ha!
return 0;
}
edit: Also, you do know that actually using iteration (loop) would be much faster? I see absolutely no point in using recursion at this particular case.
edit:
If you still don't believe me, here, another version of main():
Code:
int main() {
int arr[10];
arr[0] = 1; arr[1] = 2; arr[2] = 3; arr[3] = 1; arr[4] = 2;
arr[5] = 1; arr[6] = 2; arr[7] = 2; arr[8] = 4; arr[9] = 1;
int yet_another_variable = 1; // it will be "placed after" our array - compiled using g++ without -Ox flags
int number = count(1, arr, 10); // should return 4, since only 4 ones are in
// elements indexed from 0 to 9
std::cout << "number: " << number << "\n"; // prints "number: 5"! A-ha!
std::cout << &arr[10] << " == " << &yet_another_variable << "\n" ; // see? arr[10] is NOT part of the array! it points to yet_another_variable!
return 0;
}
Also, you should have try to compile it with optimizations on. Using g++ with flag -O3 -Werror you get:
Code:
if (integerArray[length] == numberToFind) { // integerArray[10]?!
cpp_main.cpp:8:28: error: array subscript is above array bounds
Last edited by Xupicor; September 26th, 2010 at 10:41 PM.
-
September 27th, 2010, 11:53 AM
#8
Re: Need help regarding recursion
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|