Substrings using recursive

Question

So I need to write a code using recursive method to get the substrings of the input, a proper example would be, if the input is:

"abc" the output must be: a ab abc b bc c

and so on... another example:

input: "hello" output: h he hel hell hello e el ell ello l ll llo l lo o

a=""
 if len(s)==1:
   return 
 for i in range(0,len(s)):
    for n in range(0,len(s)):   
       a+=s[i:n+1]+'\n'

this is a code that I wrote that does exactly what I need, only downside is it does not use any recursive, so if anyone could help me

Tonechas · Accepted Answer · 2016-12-14 11:13:36Z

2

Looking at your expected output, a summary of the program might be:

Write all the substrings belonging with the first char of the input string (a ab abc)
Write all the remaining substrings (b bc c)

In Python-ish pseudocode:

 def substrings(input):
      output = substrings_using_first_char(input)
      return output + substrings(input[1:])

substrings_using_first_char(), I will leave to you. It could be recursive, but there is an easy non-recursive implementation using a for loop. You could write the recursive version as an exercise.

There's a problem with the code above, however -- it always calls itself, so it will never return, and will overflow the stack. All recursive functions/methods require a stopping condition. So put one in:

 def substrings(input):
      if(input == ''):
          return []
      else:
          output = substrings_using_first_char(input)
          return output + substrings(input[1:])

This fits the universal format for recursive functions/methods:

recursiveMethod(input):
     if(input is simple case with easy answer):
         return answer for the simple case
     else:
         split input into a "small piece" and the "rest"
         return answer made by working with "small piece" and   
recursiveMethod(rest)

The whole thing can be tidied a bit, to remove the intermediate variable:

 def substrings(input):
      if(input == ''):
          return []
      else:
          return substrings_using_first_char(input) + substrings(input[1:])

I have made it return a list, rather than print to the screen, because this is generally a cleaner way to code, but you can adapt it to your needs.

Note that since Python doesn't optimize tail recursion, stack overflow is always a risk in Python. Recursion is useful (especially when working with trees) but when there's an obvious iterative solution, in Python it's usually better to use that.

edited Dec 14, 2016 at 11:13

Tonechas

13.8k16 gold badges52 silver badges85 bronze badges

answered Dec 13, 2016 at 11:28

slim

41.5k14 gold badges101 silver badges131 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Enigma Over a year ago

That is great help indeed, but you see there's more to the code and a part of it that the input should not be empty, and if it was, it should raise ValueError

slim Over a year ago

So, if input is empty, raise valueError. If input is length 1, return [ input ], else recurse.

RadekJ · Accepted Answer · 2020-04-14 15:25:56Z

0

check this:

public void test() {
    String abc = "abcdef";
    write(abc, 0, 1);
}

void write(String abc, int start, int end) {
    System.out.println(abc.substring(start, end));
    if (end == abc.length()) {
        if (start < abc.length() && start + 1 < abc.length()) {
            write(abc, start + 1, start + 2);
        }
    } else {
        write(abc, start, end + 1);
    }
}

the output is:

a
ab
abc
abcd
abcde
abcdef
b
bc
bcd
bcde
bcdef
c
cd
cde
cdef
d
de
def
e
ef
f

edited Apr 14, 2020 at 15:25

answered Dec 14, 2016 at 11:39

RadekJ

3,0731 gold badge21 silver badges29 bronze badges

2 Comments

Edwardhk Over a year ago

what about the case of bcde, bcd, bc, b...etc?

RadekJ Over a year ago

@Edwardhk you are right, I have corrected the answer

Collectives™ on Stack Overflow

Substrings using recursive

2 Answers 2

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related