Reputation: 383
In the following code, I've tried to make a recursive function to find substrings of a given string.
i = 0
j = 0
def substrings(string):
global i, j
if j == len(string) - 1 or len(string) == 0:
return []
elif i == len(string):
j = j + 1
i = j + 1
return [string[j:i]] + substrings(string)
i += 1
return [string[j:i]] + substrings(string)
>>> substrings('ceng')
>>> ['c', 'ce', 'cen', 'ceng', 'e', 'en', 'eng', 'n', 'ng', 'g']
I always tend to use globals while working with recursions, and I don't like it at all. Is there anything I can do not to use globals in this case? I know I can pass the variables to the function as parameters, but it doesn't work for me since the function is supposed to have only one parameter.
Also, if there is a way of doing this without any variable at all, I'd like to learn that too.
Upvotes: 0
Views: 1330
Reputation: 42788
The same function without recursion and global variables:
def substrings(s):
return [s[i:j] for i in xrange(0, len(s))
for j in xrange(i+1, len(s)+1)]
With recursion you probably need some inner state of your function, which must be transferred by optional parameters. You definitely can calculate the two for-loop-variables i
and j
using only the length of the returned list, but this would be cryptic and not very readable.
Upvotes: 0
Reputation:
Is something like this an option?
def substrings(string, i=0, j=0):
if j == len(string) - 1 or len(string) == 0:
return []
elif i == len(string):
j = j + 1
i = j + 1
return [string[j:i]] + substrings(string, i, j)
i += 1
return [string[j:i]] + substrings(string, i, j)
>>> substrings("ceng")
['c', 'ce', 'cen', 'ceng', 'e', 'en', 'eng', 'n', 'ng', 'g']
You don't have to give a parameter, but you can. ^^
Upvotes: 0
Reputation: 43366
If you don't want to add any parameters to the function, you can enclose a second function within it:
def substrings(string):
index= 0
length= len(string)+1
result= []
def substrings(string, index):
if index==length:
return
for i in xrange(index+1, length):
result.append(string[index:i])
substrings(string, index+1)
substrings(string, index)
return result
Upvotes: 2