CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 8 of 8
  1. #1
    Join Date
    Jul 2010
    Posts
    73

    Unhappy 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

  2. #2
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Seattle, WA
    Posts
    10,895

    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?

  3. #3
    Join Date
    Jul 2010
    Posts
    73

    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 .

  4. #4
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Seattle, WA
    Posts
    10,895

    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.

  5. #5
    Join Date
    Jul 2010
    Posts
    73

    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

  6. #6
    Join Date
    Jul 2010
    Posts
    73

    Smile 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);
    	}
    }

  7. #7
    Join Date
    Sep 2010
    Posts
    31

    Re: Need help regarding recursion

    Quote Originally Posted by Basit781 View Post
    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.

  8. #8
    Join Date
    Jul 2010
    Posts
    73

    Wink Re: Need help regarding recursion

    Hi Xupicor
    Thanks. You are right. Actually i was getting the right answer that's why i didn't notice this thing that array[10] is overflow. Anyways thanks again

    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.
    yup you are right. No need to do this using recursion. It was just an exercise that i encountered in a book that's why i gave it a try, and received such nice comments from you people

    cheers

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured