Python recursive function calls
I am trying to implement a recursive function and ran into some difficulties, I will appreciate your thoughts. As an example, try creating a function named sliding
that does this
sliding("python", 2)
["py", "yt", "th", "ho", "on"]
That is, for the selected integer, we slide along the string, grabbing substrings of the corresponding length, and then returning them all in the list.
Now that I can (stupidly) try to define this recursively:
def sliding(string,k):
return s if len(string)==k else [string[:k]].append(sliding(string[1:],k))
It will fail , mainly because it list.append()
happens in-place and returns None
. So my question is, is there a way to make such a recursive function even though there are many Python methods in practice?
Here's the best I have
def sliding(s,k):
if len(s)==k:
return s
else:
temp = [s[:k]]
temp.append(sliding(s[1:],k) )
return temp
The result is
sliding("python",k=2)
['py', ['yt', ['th', ['ho', 'on']]]]
which is obviously not exactly the desired way out, but is in the right direction. What other ways could there be? Thanks for your thoughts.
Use an operator +
to get a new concatenated list:
def sliding(s, k):
if len(s) < k: return []
else: return [s[:k]] + sliding(s[1:], k)
Solution without recursion, just a little play on the 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"]
How about this?
def sliding(string, k):
return [string[i:i+k] for i in range(len(string)-k+1)]
Here are the 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']
I would suggest:
temp.extend(sliding(s[1:],k) )
instead of adding as you will be getting a lot of objects with change.