Global variables and recursion in python

Question

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.

Why don't you just add another parameter to substrings? Confused by your statement "has to" — Duniyadnd
– Duniyadnd, Commented Dec 7, 2014 at 12:55
@Duniyadnd The function is supposed to have only one parameter, that is, string itself. It's just a constraint. — user2694307
– user2694307, Commented Dec 7, 2014 at 12:58

Aran-Fey · Accepted Answer · 2014-12-07 13:09:44Z

2

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

answered Dec 7, 2014 at 13:09

Aran-Fey

44k13 gold badges113 silver badges161 bronze badges

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

1 Comment

user2694307 Over a year ago

We musn't use any iterative tools for now (like for or while), but I got the idea that I can define an inside function. Thank you.

user4306467 · Accepted Answer · 2014-12-07 13:14:41Z

0

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. ^^

answered Dec 7, 2014 at 13:14

user4306467

1 Comment

user2694307 Over a year ago

Are those like optional parameters? You have absolutely avoided the globals, and thank you for that, but I also wanna know if there is a way to do this without any variable or parameter? Something with list slicing maybe?

Daniel · Accepted Answer · 2014-12-07 13:42:26Z

0

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.

answered Dec 7, 2014 at 13:42

Daniel

42.9k4 gold badges57 silver badges82 bronze badges

Collectives™ on Stack Overflow

Global variables and recursion in python

3 Answers 3

1 Comment

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related