C++

Forum

 
Write Backward using recursion

Naulee (26)
I'm having trouble reversing a string of n length using recursion. So far I've gotten it to print "e" and "eeeee". The current code prints "e".

I was trying to get the function to first add the last char of string s to string b, then erase that last char, continuing to shorten s in the recursion process. The function then is supposed to return as a string in reverse.

Any suggestions as to what I'm doing wrong? #include <string> is a part of the files

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
 string writeBackward(string s, int n)
{
	string b = "";

	if (n<=0)
		cout<<endl;
	else
	{
		b.push_back(s.back());
		s.pop_back();
		writeBackward(s, n-1);			
	}

	return b;
};



1
2
3
4
5
6
 
int main()
{
	cout<<"\nwriteBackward() is being tested as writeBackward(abcde, 5)"<<endl;
	cout<<writeBackward("abcde", 5)<<endl;
	return 0;
}
Last edited on
swp147 (47)
Take a look at http://www.cplusplus.com/reference/string/string/

Does std::string have push_back() or pop_back() methods?

Forget that, sorry I'm new at C++. I thought those were only vector functions.
Last edited on
swp147 (47)
There is probably a much better way to do this!

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
 
#include <iostream>
#include <string>

void writeBackward(std::string s, int n)
{
	if (n == -1)
		n = s.length();

	if (n == 0)
	{
		std::cout << std::endl;		
	}
	
	else
	{
		std::cout << s.back();
		writeBackward(s.substr(0,n-1), n-1);			
	}
}

int main(void)
{
	std::cout << "\nwriteBackward() is being tested"
		<< std::endl;
	writeBackward("abcde",-1);
	return 0;
}
Last edited on
shadowCODE (680)
A much better way
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

string writeBackward(string &s)
{
	string b(s);	//copy s to b
	reverse_copy(s.begin(),s.end(),b.begin());

	return b;
}
int main()
{
	string s = "jafar";
	cout<<writeBackward(s)<<endl;

	cin.ignore();
	return 0;
}
JayhawkZombie (738)
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
 
#include <iostream>
#include <string>

void back(std::string myStr, int index)
{

        //what should you do in here?

        //hint, when recursing, pass index - 1 to travel backwards

	back(myStr, index - 1);

}

int main()
{

	std::string myStr;
	//myStr = "BACKWARDS";
	myStr = "SDRAWKCAB"; //so, it will print normally if it works

        //this for-loop will print it backwards iteratively

        std::cout << "ITERATIVELY" << std::endl;

	for (int i = myStr.length() - 1; i >= 0; i--)
	{

		std::cout << myStr[i];
	}

	std::cout << std::endl;


	std::cout << "RECURSIVELY" << std::endl;

	//CALL "back" here
        //how should you pass the index to travel backwards
        //where should index start?


}


my output:
ITERATIVELY
BACKWARDS
RECURSIVELY
BACKWARDS
Press any key to continue . . .


ShadowCode used "algorithm", which you said you can't use.
Here is a way without that library

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
 
#include <iostream>
#include <string>

void back(std::string myStr, int index)
{

	if (index < 0)
	{
		std::cout << std::endl;
		return;
	}

	std::cout << myStr[index];

	back(myStr, index - 1);

}

int main()
{

	std::string myStr;
	//myStr = "BACKWARDS";
	myStr = "SDRAWKCAB"; //so, it will print normally if it works

	for (int i = myStr.length() - 1; i >= 0; i--)
	{

		std::cout << myStr[i];
	}

	std::cout << std::endl;


	std::cout << "RECURSIVELY" << std::endl;

	back(myStr, myStr.length() - 1);


}
Last edited on
Naulee (26)
@swp147 Well that isn't exactly the answer I'm looking for, but it does help solve a different part of the lab I'm doing that does use a void function to reverse a string... so thanks!
Last edited on
shadowCODE (680)
Must it be recursive?
Naulee (26)
Yes it must be recursive, no iteration. Sorry if I'm responding slowly, I'm still reading both codes
Naulee (26)
Okay so, I understand that using void functions to recurse the string is much better, and that is a later part of the lab I am doing, but can anyone think of a solution to my string return type
JayhawkZombie (738)
This should do the trick

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
 
#include <iostream>
#include <string>

std::string backString(std::string myStr, int index, std::string toReturn = "")
{

	if (index < 0)
	{
		return toReturn;
	}

	else
	{
		toReturn += myStr[index];
		return(backString(myStr, index - 1, toReturn));
	}

}

void back(std::string myStr, int index)
{

	if (index < 0)
	{
		std::cout << std::endl;
		return;
	}

	std::cout << myStr[index];

	back(myStr, index - 1);

}

int main()
{

	std::string myStr;
	//myStr = "BACKWARDS";
	myStr = "SDRAWKCAB"; //so, it will print normally if it works

	for (int i = myStr.length() - 1; i >= 0; i--)
	{

		std::cout << myStr[i];
	}

	std::cout << std::endl;


	std::cout << "RECURSIVELY" << std::endl;

	back(myStr, myStr.length() - 1);

	std::cout << "FROM RETURN TYPE OF STRING" << std::endl;

	std::string fromReturn = backString(myStr, myStr.length() - 1);

	std::cout << fromReturn << std::endl;

	std::cout << "DONE" << std::endl;

}
JLBorges (13770)
1
2
3
4
5
 
std::string reverse( std::string str )
{
    if( str.size() < 2 ) return str ;
    return reverse( str.substr(1) ) + str[0]  ;
}

http://coliru.stacked-crooked.com/a/87572c0b0e1c1121
Naulee (26)
Thank you for the replies! My final code for this function turned out like this:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
string b = "";
string writeBackward(string s, int n)
{

	if (n<0)
		return b;
		
	else
	{
		b += s[n];
		return writeBackward(s, n-1);			
	}

};


1
2
3
4
5
6
7
8
 
	
int main()
{
cout<<"\nwriteBackward() is being tested as writeBackward(abcde, 5)"<<endl;
	string str = "abcde";
	cout<<writeBackward(str, str.length()-1)<<endl;
return 0;
}

JayhawkZombie (738)
Considering this lab is about recursion and this problem is for a lab assignment, I don't think a course going over recursion would have covered the type of code that JLBorges posted.

In any case, his code is MUCH more efficient than mine, but I only used concepts that were available to me when I took a course that covered recursion.

Really, all you want to do is assemble a new string in reverse, and return that string when you hit the beginning of the old string (the one you are copying in reverse). Of course, to do it recursively, you'll need a base case (break condition) that stops the recursion (that's the "if (index < 0) part - it's index < 0 because you want to copy string[0] as it contains the first letter in the original string).

EDIT: I see you already got a solution. Good job.
Last edited on
Topic archived. No new replies allowed.