Thread: Recursion function won't exit

  1. #1
    Registered User
    Join Date
    Oct 2001
    Posts
    26

    Recursion function won't exit

    Listed below is a recursion function that reads a list of characters for a palindrome. The recursion goes from the inside out to the edges. ( No strings allowed ) . This function reads all the characters fine but won't jump back to the main ().

    main () uses one variable which is the number of characters in the palindrome. The function then divives the number by 2 to know how many loops in the recursion and mod 2 to deal with the odd middle character. The function reads all the number fine but never jumps back to main . help!!


    bool palindrome ( int half , int mod )
    {
    char letter1, letter2, oddletter;
    bool status = true;
    if ( half >= 1 ){
    letter1 = cin.get();
    cout << letter1;
    palindrome ( half--, mod );
    letter2 = cin.get();
    cout << letter2;
    if ( letter1 != letter2 )
    status = false;
    else
    if ( mod == 1 ) {
    oddletter = cin.get();
    cout << oddletter;
    status = true;
    }
    }

    return status;
    }

  2. #2
    of Zen Hall zen's Avatar
    Join Date
    Aug 2001
    Posts
    1,007
    The condition if ( half >= 1 ) will never be false because you post increment half when passing into palindrome, so you're always passing the same value.
    zen

  3. #3
    Registered User
    Join Date
    Oct 2001
    Posts
    26
    Thanks - but how do I decrement half. If I decrement in the first if statement if(half-- >= 1 ) then the program jumps back to main but goes into a loop in main() with no exit.

  4. #4
    of Zen Hall zen's Avatar
    Join Date
    Aug 2001
    Posts
    1,007
    I don't know without seeing main(). I'm not sure that the function works as it is, I think you need to stop calling palindrome() recursively if it ever returns false otherwise the last call will decide whether a pallindrome has been entered regardless of whether the other letters are the same (it would class a word with the same first and last letter as a pallindrome). Also if mod is one then one extra character will be inputed everytime palindrome() is called and not just one extra character, but without seeing more code I don't know if this is what you intended.
    zen

  5. #5
    Registered User
    Join Date
    Oct 2001
    Posts
    26
    Zen:

    here is the entire program. The main() seems to work fine but the bottom does not recurse as intended.

    It should: 1) get a letter 2) write a letter 3) recurse for half the number of letters 4) read & write the 2nd half 5) read and write the middle letter ( for odd numbers of characters ) 6) check for inequality 7) give true or false to main()#include <iostream>

    using std::cin;
    using std::cout;
    using std::endl;
    using std::boolalpha;

    bool palindrome(int, int);

    main()
    {
    const int StopVal = 0;
    int num;
    cout << "Enter the number of letters in your candidate palindrome, or\n"
    << "enter " << StopVal << " to end this program.\n\n";
    cout << "Enter the number of letters (" << StopVal << " to stop) here ==> ";
    cin >> num;
    cin.get( ); /* discard the after the user's numeric input here */
    while (num != StopVal) {
    cout << "Enter the palindrome candidate ==> ";
    if(palindrome(num/2, num % 2))
    cout << " is a palindrome.\n" << endl;
    else
    cout << " is not a palindrome.\n" << endl;
    cout << "Enter number of letters for the next candidate ("
    << StopVal << " to stop) ==> ";
    cin >> num;
    cin.get( ); /* discard the after the user's numeric input here */
    }
    return 0;
    }
    bool palindrome ( int half , int mod )

    {
    char letter1, letter2, oddletter;
    bool status = true;
    if ( half-1 >= 1 ){
    letter1 = cin.get();
    cout << letter1;
    palindrome ( half, mod );
    letter2 = cin.get();
    cout << letter2;
    if ( letter1 != letter2 )
    { status = false;
    if (status = false)
    return status;}
    else
    if ( mod == 1 ) {
    oddletter = cin.get();
    cout << oddletter;

    }
    status = true;
    }

    return status;
    }

  6. #6
    of Zen Hall zen's Avatar
    Join Date
    Aug 2001
    Posts
    1,007
    You'll have to move your code that checks for the middle letter and make sure it's only executed once, and you could use static variables to keep track of things -

    Code:
    #include <iostream>
    
    using namespace std;
    
    bool palindrome ( int half , int mod ) 
    { 
    	char letter1, letter2, oddletter; 
    	static bool status = true; 
    	static bool oddgot = false;
    	if ( half-- >= 1){
    		status=true;
    		oddgot=false;
    		cin >>letter1; 
    		cout << letter1;
    		palindrome ( half, mod );
    	
    		if ( mod == 1 && oddgot==false) { 
    				cin >>oddletter;
    				cout << oddletter; 
    				oddgot=true;
    		}
    			
    		cin>>letter2; 
     
    		cout << letter2;
    		if ( letter1 != letter2 ) 
    			status = false; 
    		
    	} 
    
    return status; 
    }
    
    int main() 
    { 
    	const int StopVal = 0; 
    	int num,mod=0; 
    	cout << "Enter the number of letters in your candidate palindrome, or\n" 
    	<< "enter " << StopVal << " to end this program.\n\n"; 
    	cout << "Enter the number of letters (" << StopVal << " to stop) here ==> "; 
    	cin >> num; 
    	
    	while (num != StopVal) { 
    		cout << "Enter the palindrome candidate ==> "; 
    		if(palindrome(num/2, num%2)) 
    			cout << " is a palindrome.\n" << endl; 
    		else 
    			cout << " is not a palindrome.\n" << endl; 
    		cout << "Enter number of letters for the next candidate (" 
    		<< StopVal << " to stop) ==> "; 
    		cin >> num; 
    			
    		} 
    	return 0; 
    }
    zen

  7. #7
    Unregistered
    Guest
    Zen:

    Thanks -

    This program now works except for the single character case which is by default a palindrome. It calculates the boolean true but doesn't print the character.

  8. #8
    of Zen Hall zen's Avatar
    Join Date
    Aug 2001
    Posts
    1,007
    That's because when you enter 1 and it's divided by 2 it's being truncated to zero, and half-- >=1 is never true so no characters are inputed. You could try checking and altering the input before passing it to palindrome(), but as an odd number of characters requires a minimum of three inputs within the function, you'd have to re-do alot of it.

    The simpler solution would be to check for a half value of zero within the function. If you recieve zero in your function then you know that 1 has been entered, because if you entered zero in main() then your program ends. You'd then only have to check half after it's been decremented to make sure that palindrome() is called the correct number of times -

    Code:
    bool palindrome ( int half , int mod ) 
    { 
    	char letter1, letter2, oddletter; 
    	static bool status = true; 
    	static bool oddgot = false;
    	
    	//if one character has been entered - is palindrome
    	if (half==0){
    		cin >> letter1;
    		cout << letter1;
    		return status;
    	}
    
    	if ( half-- >=1){
    		status=true;
    		oddgot=false;
    		cin >>letter1; 
    		cout << letter1;
    		if(half>0)
    	             palindrome ( half, mod );
    	
    		if ( mod == 1 && oddgot==false ) { 
    				cin >>oddletter;
    				cout << oddletter; 
    				oddgot=true;
    		}
    			
    		cin>>letter2; 
     
    		cout << letter2;
    		if ( letter1 != letter2 ) 
    			status = false; 
    		
    	} 
    
    	return status; 
    }
    zen

  9. #9
    Unregistered
    Guest
    Tried that before but is messes up the non-single character case. The palindrome is printed but not the answer " is / is not a palindrome".

    i.e. num = 5
    input asdsa
    print out asdsa

    ( must halt execution )

  10. #10
    of Zen Hall zen's Avatar
    Join Date
    Aug 2001
    Posts
    1,007
    Dunno, tried it with MSVC and Dev C++ and it appears to be working correctly, for both single and non-single cases. Have you changed everything?
    zen

  11. #11
    Unregistered
    Guest
    Everything was changed. The program works fine for all non-single character attempts. When the 'single case' is added, it fails on all but the single character case. using MS Visual C++

  12. #12
    of Zen Hall zen's Avatar
    Join Date
    Aug 2001
    Posts
    1,007
    hmm.. it's working fine for me. Can you post your full code?
    zen

  13. #13
    Registered User
    Join Date
    Oct 2001
    Posts
    26
    Here is a copy of the code that hangs. Meaning it print the palindrome & stops.

    I the half == 0 code is commented out, the program runs fine for characters 2 and up. ????#include <iostream>


    using std::cout;
    using std::cin;
    using std::endl;
    using std::boolalpha;

    bool palindrome (int, int);

    int main()
    {
    const int StopVal = 0;
    int num,mod=0;
    cout << "Enter the number of letters in your candidate palindrome, or\n"
    << "enter " << StopVal << " to end this program.\n\n";
    cout << "Enter the number of letters (" << StopVal << " to stop) here ==> ";
    cin >> num;

    while (num != StopVal) {
    cout << "Enter the palindrome candidate ==> ";
    if(palindrome(num/2, num%2))
    cout << " is a palindrome.\n" << endl;
    else
    cout << " is not a palindrome.\n" << endl;
    cout << "Enter number of letters for the next candidate ("
    << StopVal << " to stop) ==> ";
    cin >> num;

    }
    return 0;
    }

    bool palindrome ( int half , int mod )
    {
    char letter1, letter2, oddletter;
    static bool status = true;
    static bool oddgot = false;

    if ( half == 0 ) {
    cin >> letter1;
    cout << letter1;
    return status;
    }

    if ( half-- >= 1){
    status=true;
    oddgot=false;
    cin >>letter1;
    cout << letter1;
    palindrome ( half, mod );

    if ( mod == 1 && oddgot==false) {
    cin >>oddletter;
    cout << oddletter;
    oddgot=true;
    }

    cin>>letter2;
    cout << letter2;
    if ( letter1 != letter2 )
    status = false;



    }
    return status;
    }

  14. #14
    of Zen Hall zen's Avatar
    Join Date
    Aug 2001
    Posts
    1,007
    You haven't put the code in to ensure that palindrome() is only being called recursively if half is > 0. Re-check the code from my previous post (the last one with code in).
    zen

  15. #15
    Registered User
    Join Date
    Oct 2001
    Posts
    26

    Smile

    You are correct Zen. That line did it. However, the single character case ( half == 0 ) will only work if I add status = true; to that bit of code. Without it, it says that " is not a palindrome." Otherwise, all is good.

    I tip my hat to you.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. doubt in c parser coding
    By akshara.sinha in forum C Programming
    Replies: 4
    Last Post: 12-23-2007, 01:49 PM
  2. Odd memory leaks
    By VirtualAce in forum C++ Programming
    Replies: 11
    Last Post: 05-25-2006, 12:56 AM
  3. Including lib in a lib
    By bibiteinfo in forum C++ Programming
    Replies: 0
    Last Post: 02-07-2006, 02:28 PM
  4. c++ linking problem for x11
    By kron in forum Linux Programming
    Replies: 1
    Last Post: 11-19-2004, 10:18 AM
  5. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM