Как получить все последовательные подстроки строки с рекурсией?

Question

Это итеративная версия. Как получить тот же результат с помощью рекурсивного кода?

def it(word): 
    set1 = set() 
    for begin in range(len(word)): 
     for end in range(begin,len(word)): 
     set1.add(word[begin:end+1]) 
return set1 

Это то, что у меня есть, но это не дает каждый подстроки назад

def recursievesubstring(string): 
    lijst = [] 
    if len(string) == 0: 
     lijst.append("") 
    else: 
     i = 0 
     if len(string) > 1: 
      midden = len(lijst)//2 
      lijst.append(string[midden+1]) 
     while i < len(string): 
      lijst.append(string[:i]) 
      lijst.append(string[i:]) 
      recursievesubstring(string[i:-i]) 
      i+=1 
    return lijst 

def main(): 
    string = input("Geef een woord: ") 
    print(recursievesubstring(string)) 

Answer 1

Что делает это сложным, так это то, что у вас двойная итерация, поэтому один способ атаковать это, делая рекурсивную функцию для каждого цикла и объединяя их, это означает вспомогательную функцию, которая обрабатывает внутренний цикл и главный, которые обрабатывают внешний контур.

Для этого мы должны понять работу итерационной функции, простая печать поможет

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 

и простой тест выявить полезный образец

>>> x=it("abcdef") 
a 
ab 
abc 
abcd 
abcde 
abcdef 

b 
bc 
bcd 
bcde 
bcdef 

c 
cd 
cde 
cdef 

d 
de 
def 

e 
ef 

f 

>>> 

, которые делают задачу более clear, вспомогательная функция принимает строку и либо удаляет последний символ, либо каждый раз подбирает более строчную строчку, а основная функция удаляет первый символ в каждом рекурсивном вызове.

Теперь я не дал бы вам рабочий код, но шаблон, который используют tail recursion, для вас, чтобы закончить

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 

дать ему попробовать, и проверить это, как это, например

>>> it("abcdef") == recur("abcdef") 

Answer 2

Вы должны сделать вспомогательные методы, которые могут принимать более аргументов. (Рекурсия хвоста) Если ограничение состоит в том, чтобы написать рекурсивную функцию, вы не можете использовать какие-либо петли for или while.