Recursive Function that returns all substrings of a string
In your assignment there is written that the recursive function has to be declared like
vector<string> generateSubstrings(string s),
But you are trying to make another function recursive that declared like
vector<string> generateSubstrings(string s, int num);
So in any case your solution does not satisfy the requirement of the assignment.
The function can look the following way
#include <iostream>
#include <string>
#include <vector>
std::vector<std::string> generateSubstrings( std::string s )
{
if ( s.empty() ) return {};
std::vector<std::string> v;
v.reserve( s.size() * ( s.size() + 1 ) / 2 );
for ( std::string::size_type i = 0; i < s.size(); i++ )
{
v.push_back( s.substr( 0, i + 1 ) );
}
for ( const std::string &t : generateSubstrings( s.substr( 1 ) ) )
{
v.push_back( t );
}
return v;
}
int main()
{
std::string s( "rum" );
for ( const std::string &t : generateSubstrings( s ) )
{
std::cout << t << std::endl;
}
return 0;
}
Its output is
r
ru
rum
u
um
m
If you need also to include an empty string then you should change condition
if ( s.empty() ) return {};
in appropriate way. For example
if ( s.empty() ) return { "" };
Also in this case you should write
v.reserve( s.size() * ( s.size() + 1 ) / 2 + 1 );
Also you can replace the loop in the shown function with method insert. For example
#include <iostream>
#include <string>
#include <vector>
std::vector<std::string> generateSubstrings( std::string s )
{
if ( s.empty() ) return {};
std::vector<std::string> v;
v.reserve( s.size() * ( s.size() + 1 ) / 2 );
for ( std::string::size_type i = 0; i < s.size(); i++ )
{
v.push_back( s.substr( 0, i + 1 ) );
}
std::vector<std::string> v2 = generateSubstrings( s.substr( 1 ) );
v.insert( v.end(), v2.begin(), v2.end() );
return v;
}
int main()
{
std::string s( "rum" );
for ( const std::string &t : generateSubstrings( s ) )
{
std::cout << t << std::endl;
}
return 0;
}
The program output will be the same as shown above.
Here is a program modification that includes an empty string in the vector.
#include <iostream>
#include <string>
#include <vector>
std::vector<std::string> generateSubstrings( std::string s )
{
if ( s.empty() ) return { "" };
std::vector<std::string> v;
v.reserve( s.size() * ( s.size() + 1 ) / 2 + 1 );
for ( std::string::size_type i = 0; i < s.size(); i++ )
{
v.push_back( s.substr( 0, i + 1 ) );
}
std::vector<std::string> v2 = generateSubstrings( s.substr( 1 ) );
v.insert( v.end(), v2.begin(), v2.end() );
return v;
}
int main()
{
std::string s( "rum" );
for ( const std::string &t : generateSubstrings( s ) )
{
std::cout << t << std::endl;
}
return 0;
}
Java - using recursion to create all substrings from a string
The following turned out to be the best solution:
public class recursive {
static String in = "1234";
public static void main(String[] args) {
substrings(0,1);
}
static void substrings(int start, int end){
if(start == in.length() && end == in.length()){
return;
}else{
if(end == in.length()+1){
substrings(start+1,start+1);
}else{
System.out.println(in.substring(start, end));
substrings(start, end+1);
}
}
}
}
It first checks the base case: if both start and end are equal to in.length().
Because if they are, that means there are no more substrings to be found, and the program ends.
Let's start with start=0 and end=1. They obviously don't equal in.length(), and end definitely doesn't equal in.length()+1.
Thus, substring(0,1) will be printed out, which is 1.
The next iteration of substrings will be substrings(0,2), and in.substring(0,2) will be printed, which is 12. This will continue until end == in.length()+1, which happens when the program finishes substrings(0,4) and tries to move on to substrings(0,5).
5 == in.length()+1, so when that happens, the program will do substrings(start+1,start+1), which is substrings(1,1). The process will continue with substrings(1,2), and (1,3), until (1,5) when the program will run substrings(2,2).
All of this will continue until substrings(4,4), which, at that point, the program stops.
The result looks like this:
1
12
123
1234
2
23
234
3
34
4
How do I get all consecutive substrings of a string with recursion?
what make this complicated is that you have a double iteration, so one way to attack this making a recursive function for each loop and combine them, this mean a auxiliary function that handle the inner loop and the main one that handle the outer loop.
To that end we need to understand the working of the iterative function, a simple print will help
def it(word):
set1 = set()
for begin in range(len(word)):
for end in range(begin,len(word)):
set1.add(word[begin:end+1])
print(word[begin:end+1])
print()
return set1
and a simple test reveal a useful pattern
>>> x=it("abcdef")
a
ab
abc
abcd
abcde
abcdef
b
bc
bcd
bcde
bcdef
c
cd
cde
cdef
d
de
def
e
ef
f
>>>
which make the objective more clear, the auxiliary function take a string and either remove the last character or take a sub-string more larger each time, while the main function would remove the first character in each recursive call.
Now I would not give you an working code, but a template, that use tail recursion, for you to complete
def recur_aux(word, result=None, end=None):
if result is None:
result = set()
if end is None:
end = # an adequate default value
if #an adequate stop condition, aka base case:
return result
else:
#do an adequate step
return recur_aux( word, result, #end + or - 1 )
def recur(word,result=None):
if result is None:
result = set()
if word: #this is equivalent to len(word)!=0
#do a adequate step calling recur_aux
return recur( # an adequate recursive call )
else:
return result
give it a try, and test it like this for example
>>> it("abcdef") == recur("abcdef")
Generate consecutive substring from the string using recursion
With recursion, you might do:
void print_seq(std::string_view s)
{
if (s.size() > 1) print_seq(s.substr(0, s.size() - 1));
std::cout << s << std::endl;
}
void print_all(std::string_view s)
{
print_seq(s);
if (s.size() > 1) print_all(s.substr(1));
}
int main()
{
print_all("ABCD");
}
Demo
Related Topics
How to Read N Bytes from a File and Put Them into a Vector<Uint8_T> Using Iterators
How to Best Silence a Warning About Unused Variables
When Should Static_Cast, Dynamic_Cast, Const_Cast, and Reinterpret_Cast Be Used
Undefined Reference to 'Winmain@16'
Difference Between New/Delete and Malloc/Free
Is Local Static Variable Initialization Thread-Safe in C++11
Why Is Enum Class Preferred Over Plain Enum
Is There a Standard Sign Function (Signum, Sgn) in C/C++
How to Check Whether a String Contains Every Letter in the Alphabet in C++
Forcing the Qt Gui to Update Before Entering a Separate Function
How to Declare a 2D Array in C++ Using New
Why Do People Say There Is Modulo Bias When Using a Random Number Generator
Cin and Getline Skipping Input
Use of 'Const' For Function Parameters
Function With Same Name But Different Signature in Derived Class