Entonces necesito escribir un código usando un método recursivo para obtener las subcadenas de la entrada, un ejemplo adecuado sería, si la entrada es:

"abc" la salida debe ser: a ab abc b bc c

Y así sucesivamente ... otro ejemplo:

entrada: "hola" salida: h el infierno hola 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'

Este es un código que escribí que hace exactamente lo que necesito, el único inconveniente es que no usa ningún recursivo, así que si alguien pudiera ayudarme

0
Enigma 13 dic. 2016 a las 14:00

2 respuestas

La mejor respuesta

En cuanto a su resultado esperado, un resumen del programa podría ser:

  1. Escriba todas las subcadenas que pertenecen al primer carácter de la cadena de entrada (a ab abc)
  2. Escriba todas las subcadenas restantes (b bc c)

En pseudocódigo similar a Python:

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

substrings_using_first_char(), te lo dejo a ti. Podría ser recursivo, pero hay una implementación no recursiva fácil usando un ciclo for. Podría escribir la versión recursiva como ejercicio.

Sin embargo, hay un problema con el código anterior: siempre se llama a sí mismo, por lo que nunca regresará y desbordará la pila. Todas las funciones / métodos recursivos requieren una condición de parada. Así que pon uno en:

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

Esto se ajusta al formato universal para funciones / métodos recursivos:

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)

Todo se puede arreglar un poco, para eliminar la variable intermedia:

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

He hecho que devuelva una lista, en lugar de imprimirla en la pantalla, porque esta es generalmente una forma más limpia de codificar, pero puede adaptarla a sus necesidades.


Tenga en cuenta que, dado que Python no optimiza la recursividad de la cola, el desbordamiento de la pila siempre es un riesgo en Python. La recursividad es útil (especialmente cuando se trabaja con árboles) pero cuando hay una solución iterativa obvia, en Python generalmente es mejor usarla.

1
Tonechas 14 dic. 2016 a las 11:13

Mira esto:

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);
    }
}

La salida es:

a
ab
abc
abcd
abcde
abcdef
b
bc
bcd
bcde
bcdef
c
cd
cde
cdef
d
de
def
e
ef
f
0
RadekJ 14 abr. 2020 a las 15:25