Interesting recursion problem 12 Nov, 2009 Interesting recursion problem

Found this interesting recursion problem on StackOverflow. http://stackoverflow.com/questions/1705374/how-to-capture-a-string-into-variable-in-a-recursive-function

int resultSize( vector< vector<string> > vector ){
    int x=1;
    for( int i=0; i<vector.size(); i++ )
       x *= vector[i].size();
    return x;
}

vector<string> enumAll(const vector< vector > allVecs ){
    //__ASSERT( allVecs.size() > 0 );
    vector result;
    if( allVecs.size() == 1 ){
        for( int i=0 ; i< allVecs[0].size(); i++){
	    result.push_back( allVecs[0][i] );
        }
    return result;
    }
    const vector< vector<string> > tempVector(allVecs.begin()+1, allVecs.end() );
    vector tempResult = enumAll( tempVector );// recurse
    int size = resultSize( tempVector );
    for( int i=0; i<allVecs[0].size(); i++ ){
       for( int j=0; j<size; j++){
          //enumAll on each tempVector is called multiple times. Can be optimzed.
          result.push_back( allVecs[0][i] + tempResult[j] );
        }
    }
}

Also see the other solution by Young which solves this problem using tail-recursion.

It is interesting problem in itself to transform a plain recursion into tail-recursion. The general method to do this is to eliminate the need for any processing post recursion. For this, one needs to pass all the data as parameters. This is pretty obvious when comparing the two solutions. Plain recursion takes only one parameter, while tail-recursion takes a lot more parameters.

In my view, the advantage of plain recursion is pedagogy: it is very easy to follow the algorithm - the divide and conquer is so very obvious! With tail-recursion, we manually do a lot of book-keeping. This part is not so obvious in the present example.

Plain recursion: http://stackoverflow.com/questions/1705374/how-to-capture-a-string-into-variable-in-a-recursive-function/1723192#1723192

Tail Recursion: http://stackoverflow.com/questions/1705374/how-to-capture-a-string-into-variable-in-a-recursive-function/1707808#1707808



Tags  ·   algorithm  ·   recursion  ·   Show Comments ▾


     
Original design for Tumblr crafted by Prashanth Kamalakanthan.
Adapted for Tumblr & Jekyll by Sai Charan. Customized theme available on Github.

Sai Charan's blog by Sai Charan is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.
Creative Commons License