recursion

when i input 231 -> base to is 11100111

it pass all the false and returned true

but after return true it returning false again...

i thought after u return something the loop should be ended


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool palindrome_2(vector<int>&vec,int begin,int end){
    
    if(begin >= end) {
        cout << "returning true..."<<endl;
        return true;
    }
     
    
    if( vec[begin] != vec[end]  ) {
        cout << vec[begin] << " and " << vec[end] <<endl;
        cout << " returning false..."<<endl;
        return false;
    }

     palindrome_2(vec,begin+1,end-1);
    
        
    
}




231
result....
returning true... ( it already return true but why it keep going )
2 and 0            ( i already check vector value is 11100111 i don't 
 returning false...    understand what 2 and 0 value is come from)
2 and 1
 returning false...
4 and 1
 returning false...
1 and 3
 returning false...
4 and 0
 returning false...
3 and 7
 returning false...
2 and 6
 returning false...
1 and 0
 returning false...
1 and 3
 returning false...
1 and 10
 returning false...
1 and 7
 returning false...
1 and 6
 returning false...
1 and 7
 returning false...
 is not palindrome




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int main (int argc, const char * argv[])
{
    int palin;
    vector<int> str;
    bool result;
    vector<int> resultVec;
    
    while(true){
        cin >> palin;
        if(palin ==0) return 0;
        
        cout << "result...." <<endl;
        result = false;
        
        
        clear(str);
        base2(palin,str);
        
        //print(str);
        
        if(palindrome_2(str,0,(str.size()-1))==true) {
            
            result = true;
        
        }
            clear(str);
            base3(palin, str);
        if(palindrome_2(str,0,str.size()-1) ==true){ 
            result = true;}
            
            clear(str);
            base4(palin,str);



1
2
3
4
5
6
7
8
9
10
11
12
void base2(int num,vector<int>& str){
   
        
    if( num <=0) return 0;
   
    base2(num/2,str);
    //cout << "pushing back.."<< num%2 << endl;
    str.push_back(num%2);
    //cout << num%2;
    
    
}
Last edited on
Please enter your complete program, i.e. the main() from where you creating the vector and calling this function.
Well, you call palindrome_2 several times from your main function. Thus the multiple returns. The first call confirms that the number 231 is palindrome in base-2, but the next call states that it is not a palindrome in base-3 (22120), and it outputs exactly that - 2 is not equal to 0. The same goes for base-4, base-5, etc.

I don't see a reason to make the palindrome_2 function recursive - an iterative version would be more efficient, and in my opinion, more readable.

One more thing. You should propagate the return value from a recursive call to palindrome_2 (the compiler should give you a warning about this). To do that - change line 15 of your first code snippet to
return palindrome_2(vec,begin+1,end-1);

And the function base2 doesn't specify any return value, so instead of return 0; you should write just a simple return;. And again, iterative version would be more efficient and readable.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool palindrome_2(vector<int>&vec,int begin,int end){
    
    if(begin >= end) {
        //cout << "returning true..."<<endl;
        return true;
       
    }
     
    
    if( vec[begin] != vec[end]  ) {
        //cout << vec[begin] << " and " << vec[end] <<endl;
        //cout << " returning false..."<<endl;
        return false;
            }

     return palindrome_2(vec,begin+1,end-1);
    
        
    
}


can you explain what return do for return palindrome_2(vec,begin+1,end-1)?
so, recursive function saved (begin+1,end-1) value in the stack
and return required to call this saved value( in the stack) from the function ?

and why

1
2
3
4
5
6
7
8
9
10
11
12
void base2(int num,vector<int>& str){
   
        
    if( num <=0) return 0;
   
    base2(num/2,str);
    //cout << "pushing back.."<< num%2 << endl;
    str.push_back(num%2);
    //cout << num%2;
    
    
}


does not work with return base2(num/2,str)..

I'm using recursive because try to understand this mechanism

Basically, recursive function call is the same as any other function call. The function parameters are put onto stack, and then the function is executed in the same way it is done for the call from main (local variables are allocated on stack and they have no connection to the ones that were allocated on the first call, etc.). When this recursive call returns, the control goes to the point where this recursive call was made.

When you write return palindrome_2(vec,begin+1,end-1); it essentially means "The result that should be returned to the caller, is equal to the result returned by palindrome_2 with the following parameters: vec, begin+1, end-1". If it makes it more clear, the following code does pretty much the same thing in a more verbose way:
1
2
bool result = palindrome_2(vec,begin+1,end-1);
return result;


For the base2 function - you declare that it doesn't return any value - the representation of the number in binary form is accumulated in the parameter str that is passed by reference (which basically means that the vector passed into this function is modified directly, but this is a slightly different topic, not specific to recursion).

So as long as you understand how normal functions work (how parameters, local variables and return values are handled) you should be able to understand how the recursive calls operate: they are exactly the same as normal function calls.

Hope this clears up things a bit. If not - just ask about the things that confuse you.
Topic archived. No new replies allowed.