python recursive function calls

Question

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.

Are you aware of the `+` operator for lists? – Nayuki May 01 '15 at 18:41 — Nayuki, May 01 '15 at 18:41
Maybe change append to extend – David Greydanus May 01 '15 at 18:42 — David Greydanus, May 01 '15 at 18:42

score 5 · Accepted Answer · answered May 01 '15 at 18:43

5

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)

answered May 01 '15 at 18:43

Nayuki

17,911
6
53
80

score 3 · Answer 2 · edited May 23 '17 at 12:06

3

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"]

edited May 23 '17 at 12:06

Community

1
1

answered May 01 '15 at 18:44

Łukasz Rogalski

22,092
8
59
93

score 1 · Answer 3 · answered May 01 '15 at 18:44

1

How about this?

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

answered May 01 '15 at 18:44

Brent Washburne

12,904
4
60
82

Saksham Varma · Answer 4 · 2015-05-01T19:26:09.090

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']

score 0 · Answer 5 · answered May 01 '15 at 18:49

0

I'd suggest:

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

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

answered May 01 '15 at 18:49

CristiFati

38,250
9
50
87

python recursive function calls

5 Answers5