CODEWITHSUNDEEP
pythonrecursion
keegan
keegan

Reputation: 2992

python recursive function calls

I'm trying to implement a recursive function and have run into some difficulties, would appreciate your thoughts. As an example, let's try to create a function called sliding that does this 

sliding("python", 2)
["py", "yt", "th", "ho", "on"]

That is, for the chosen integer, we slide along the string, grabbing substrings of the appropriate length, and then return them all in a list.

Now here's how I might (foolishly) try to define this recursively:

def sliding(string,k):
  return s if len(string)==k else [string[:k]].append(sliding(string[1:],k))

This will not work, mainly because list.append() happens in place and returns a None. So my question is - Is there a way to do this kind of recursive function even though lots of Python methods occurs in place?

Here's the best I've got so far,

def sliding(s,k):
    if len(s)==k:
        return s
    else:
        temp = [s[:k]]
        temp.append(sliding(s[1:],k) ) 
        return temp

This results in

sliding("python",k=2)
['py', ['yt', ['th', ['ho', 'on']]]]

which is obviously not quite the desired output, but is in the right direction. What other ways might there be to do this? Thanks for your thoughts.

Upvotes: 3

Views: 499

Answers (5)

Saksham Varma
Saksham Varma

Reputation: 2140

Here are both iterative and recursive versions:

def sliding(s, window=2):
    for ind in range(len(s) - (window - 1)):
        yield s[ind:ind+window]


def sliding_recursive(s, window=2, ind=0):
    if ind > len(s) - window:
        return []
    strings = [s[ind: ind+window]] + sliding_recursive(s, window, ind+1)
    return strings


>>> list(sliding('python'))
['py', 'yt', 'th', 'ho', 'on']
>>> list(sliding('python', window=3))
['pyt', 'yth', 'tho', 'hon']

>>> sliding_recursive('python')
['py', 'yt', 'th', 'ho', 'on']
>>> sliding_recursive('python', window=3)
['pyt', 'yth', 'tho', 'hon']

Upvotes: 1

CristiFati
CristiFati

Reputation: 41186

I'd suggest:

temp.extend(sliding(s[1:],k) )

instead of append since you'll be getting lots of imbricated objects.

Upvotes: 0

Łukasz Rogalski
Łukasz Rogalski

Reputation: 23261

Solution without recursion, just small play on slice syntax.

def sliding(s, i):
    return [s[n:n+i] for n in xrange(len(s)-i+1)]

assert sliding("python", 2) == ["py", "yt", "th", "ho", "on"]
assert sliding("python", 3) == ["pyt", "yth", "tho", "hon"]

Upvotes: 3

Brent Washburne
Brent Washburne

Reputation: 13158

How about this?

def sliding(string, k):
    return [string[i:i+k] for i in range(len(string)-k+1)]

Upvotes: 1

Nayuki
Nayuki

Reputation: 18552

Use the + operator to get a new concatenated list:

def sliding(s, k):
    if len(s) < k: return []
    else: return [s[:k]] + sliding(s[1:], k)

Upvotes: 5

Related Questions