Recursive function problem

Hi all,
I am writing a code that will print all odd indices of a string in original order, and then all even indices of a string in reverse order.

abcdef would be printed like this: bdfeca.

The code prints bdf fine but then the confusion starts.
I have been going over it for hours now -- there is a problem with return(s[0]), wierd tho because I have used the exact same thing in other codes before ....
very greatful for your hints and tips!!
Thanks!!

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 #include <iostream>
using namespace std;

string s;

int lenght(string s, int i){
	if (s[i]=='\0')
		return (0);
	else return (1 + lenght(s, i+1));
	}

string even (string s, int l){ //reading string from end to beginning
	if (l<=0)
		return (s);
	else 	
		if(l%2)                   //odd last indices	
		        return (s[l-1] + even(s, l-2));
		else                      //even last indices
			return (s[l] + even(s, l-2));

	}

string odd (string s, int i){ //reading string from beginning to end
	if (s[i+1] == '\0')
		return (s[0]);
	else 
		return (s[i+1] + odd(s, i+2));
	}

string mix(string s, int i, int l){
	return odd(s, i);
	return even(s, l);
	}
		
int main(){
	int i = 0;
	cout << "Specify string ...";
	cin >> ::s;

	int l = lenght(::s, i);
	l = l -1;

	cout << mix(::s, i, l) << endl;

	return 0;

	}
Last edited on
closed account (D80DSL3A)
I think it can be done a bit simpler.
For comparison, this seems to be working. Recursion is subtle.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <string>

// show elements: odd forward, even reversed
void show_ofer( const std::string& s, size_t i=0 )
{
    if( i == s.size() ) return;

    if( i%2 == 1 ) std::cout << s[i];// odd i on the way in
    show_ofer( s, i+1 );
    if( i%2 == 0 ) std::cout << s[i];// even i on the way out
}

int main()
{
    show_ofer( "abcdef" );// bdfeca

    return 0;
}
Thank you so much for your reply!! Looks great - unfortunately I don't (yet) use external libraries - complete beginner.

It would be great if you could explain the logic behind your code -- i don't completely get it. Is "On the way out" referring to recursion back to where the function was called??


Thanks again!
Last edited on
i have modified my code according to your example
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
#include <iostream>
using namespace std;

int lenght(const string& s, int i){
	if (s[i]=='\0')
		return (0);
	else return (1 + lenght(s, i+1));
	}

string mix(string s, int i, int l)
{
    if(i == l) return ('\0');

    if(i%2 == 1) 
	cout << s[i];   
    mix( s, i+1, l);
    if(i%2 == 0) 
	cout << s[i];   
}

int main(){
    int i=0;
    string s;
    cout << "Specify string ...";
    cin >> s;
    int l = lenght(s, i);
    cout << mix(s,i,l) << endl;     

    return 0;
}


The compiler throws a warning
1
2
3
111.C: In function ‘std::string mix(std::string, int, int)’:
111.C:21:1: warning: control reaches end of non-void function [-Wreturn-type]
 }


then, when compiling an error
1
2
3
terminate called after throwing an instance of 'std::logic_error'
  what():  basic_string::_S_construct null not valid
bdfAborted (core dumped)


Is this the case because the end condition of the recursion is wrong (i==l)?
Many thanks for your help!!
closed account (D80DSL3A)
Glad you found that helpful. I can't help much with your mix function. It's supposed to return a string, but only does so on line 12. When it returns following line 18 what value is returned? If mix returns a value it's not being utilized on line 16.
What kind of strings are you using? I had assumed the c++ string class, but clearly not. I see no #include for anything.
The terminating condition based on finding the '\0' should work fine in the function I posted:
1
2
3
4
5
6
7
8
void show_ofer( const string& s, size_t i=0 )
{
    if( s[i] == '\0' ) return;

    if( i%2 == 1 ) std::cout << s[i];// odd i on the way in
    show_ofer( s, i+1 );
    if( i%2 == 0 ) std::cout << s[i];// even i on the way out
}

That mix function is gonna be your baby. Why does it need to stream: cout << mix(s,i,l) << endl;. There are cout statements in the function. You could just call it:
mix(s); then it doesn't have to return a string.

edit: Do you want the function to produce a string with elements in the given order, then cout the string?
This version will produce a string Copy:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void getStr_ofer( string& Copy, const string& sce, size_t i=0 )
{
    if( sce[i] == '\0' ) return;

    if( i%2 == 1 ) Copy += sce[i];
    getStr_ofer( Copy, sce, i+1 );
    if( i%2 == 0 ) Copy += sce[i];
}

int main()
{
    string copyStr;
    getStr_ofer( copyStr, "abcdef" );
    cout << '\n' << copyStr;

    return 0;
}

Operator += maybe not supported by your string class? push_back(string)? append(string)? Any of those would do.
Last edited on
Thanks for your comments!!! Especially that one about not using cout << mix(s,i,l), simple enough but didn't think about it - so, thanks again, wouldn't have done it without your help!

the working (still a little complicated ;)) mix function:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void mix(string s, int i, int l){ //l lenght of string
    if(i >= l){
	i = l-1;
	if (i%2 == 0){            //last Indices even
		cout << s[i];
		i = i-1;	
		}
	}
    if(i%2 == 0) {
	cout << s[i+1]; 
	mix(s, i+2, l);  
	}
    if(i%2 == 1) {
        cout << s[i-1];
	mix(s, i-2, l);
	}
    if(i<0)
        cout << endl;
	return;
}

Topic archived. No new replies allowed.