Very quick and easy homework question. I have it running ok but I think there's a better
way to do it. A more Pythonic way.
Here's my code to recursively decrement each element of a list by 1.
l = range(30)
def recurseDecrMap(l, x = []):
if len(l) == 0:
return []
else:
x.append(l[0] -1)
recurseDecrMap(l[1:], x)
return x
So thanks for any input. I'm trying to learn to do better recursion. Having trouble getting
the knack of it.
You can use only one argument, in my opinion it is simpler:
def recurseDecrMap(l):
if not l:
return []
else:
return [l[0]-1] + recurseDecrMap(l[1:])
But as @jamylak pointed out, the complexity of this algorithm is O(N^2), since l[1:] creates a new list with references to the rest of the items in the list.
If you need efficiency, I'd recommend you using list comprehensions (Haidro's answer), but I suppose it is not a priority if you want it only for learning purposes.
Probably less pythonic, but there:
def recurseDecrMap(l):
return [l[0]-1] + recurseDecrMap(l[1:]) if l else []
For what it's worth, this is a terrible way to learn about recursion, because you're using it to do something that is not inherently recursive. If your teacher really is asking you to write a program that decrements the elements of a list like [1, 2, 3, 4] recursively, then shame on him/her.
As Haidro noted, the most Pythonic way to solve this problem is to just iterate over the list using a list comprehension
[i - 1 for i in l]
As a loop, this is
def decr(l):
a = []
for i in l:
a.append(i - 1)
return a
Recursion is useful if you want to solve the same problem at arbitrary levels of depth. For example, say you had something like [1, [2, 3], [[4], 5]] and you wanted to decrement each number by 1, while maintaining the list structure. In that case, a recursive solution would use the iterative solution for the base case, and call itself for the recursive case.
def decr_recursive(l):
a = []
for i in l:
if isinstance(i, list):
a.append(decr_recursive(i))
else:
a.append(i - 1)
return a
This can be easily modified if you want to support more than just lists or integers.
>>> decr([1, [2, 3], [[4], 5]])
[0, [1, 2], [[3], 4]]
This is the sort of problem that is very difficult to solve without using recursion, but is easy to solve with it. What you are asking is the sort of problem that is easy to solve without recursion (it's just a simple iteration over a list for God's sake), but somewhat difficult to solve with it.
Some reasons why you should avoid recursion in Python
It's harder to read. Compare [i - 1 for i in l], or even the explicit loop, to something like
def decr(l):
if not l:
return []
return [l[0] - 1] + decr(l[:1])
Calling a function in Python can be expensive. I get roughly the same timings as Ashwini Chaudhary on my computer. But [i - 1 for i in range(10**4)] takes 559 µs on my computer. That's three orders of magnitude faster than the fastest recursive method.
Recursive functions don't work past 1000 calls unless you set the recursion limit higher. You may have noticed the sys.setrecursionlimit(10**5) call in Ashwini Chaudhary's answer. This is necessary because without it, each call would lead to a RuntimeError: maximum recursion depth exceeded following a huge traceback. But even with this, a little bigger list would still lead to a recursion limit. And according to the documentation, there is a top limit for every OS, and setting it too high can lead to a crash.
Recursive functions are harder to debug. Not only do they pollute your stack traces with hundreds of calls from the same function, but they are conceptually harder to follow, because the same part of the same function is being used in different ways, depending on which level in the stack you are in. The natural human way of thinking is iterative. We do things one at a time. Our own brains' "stacks" are only a few levels deep, so we have a very hard time solving problems in a recursive way, like "let me start solving a problem, but before I finish, let me solve another problem, and then when I'm done, I'll finish the original problem. And in the smaller problem, I may do the same thing, so that I get several levels deep before I finish." That's why you walk into the kitchen to get a pen, then you see a candy bar and start eating it, and when you are done, you forget about the pen. You "recursed" a level, from the pen problem to the candy bar problem, and your mental stack got too deep (just two levels, but that's enough). If you had instead grabbed the candy bar, but before you opened it and started eating it, also found the pen (the best iterative analouge I could come up with), you would do both without forgetting either. The way you should solve problems in programs should be exactly the same way you solve them in your head, because that's the only way you will understand what your code is doing. Python is such a great language because its high level interface let's you do exactly that (at least more often than in lower-level languages). Use this fact!
Here's the worst way - using Fixed Point Combinator:
Y = lambda g: (lambda f: g(lambda arg: f(f)(arg))) (lambda f: g(lambda arg: f(f)(arg)))
recurseDecrMap = Y(lambda f: lambda l: [l[0]-1] + f(l[1:]) if l else [])
Here's a simple pythonic way:
>>> mylist = range(30)
>>> def func(l):
... return [i-1 for i in l]
>>> func(mylist)
[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28]
Explanation:
I used list comprehensions to create a new list of every element in mylist whose value is one less than what it was.
There's nothing wrong with your piece of code, except if you're going to use it more than once:
>>> recurseDecrMap(l)
[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28]
>>> recurseDecrMap(l)
[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28]
To avoid this, check out this answer.
Timing comparisons of various ways to do this:
In [1]: import sys
In [2]: sys.setrecursionlimit(10**5)
In [3]: from so import *
In [4]: %timeit recur(range(10**4)).show()
10 loops, best of 3: 18.2 ms per loop
In [5]: %timeit recurse1(range(10**4))
1 loops, best of 3: 559 ms per loop
In [6]: %timeit recurse2(range(10**4))
1 loops, best of 3: 1e+03 ms per loop
In [7]: %timeit recurse3(range(10**4))
1 loops, best of 3: 1.02 s per loop
In [8]: %timeit recurse4(range(10**4))
1 loops, best of 3: 596 ms per loop
Code:
class recur:
# No extra memory is required in this method
def __init__(self,lis):
self.lis=lis
self.len=len(self.lis)
self.rec(0)
def show(self):
return self.lis
def rec(self,n):
if n!=self.len:
self.lis[n]-=1
self.rec(n+1)
def recurse1(l,lis=None):
lis=lis if lis is not None else []
if l:
lis.append(l[0]-1)
return recurse1(l[1:],lis)
else:
return lis
def recurse2(l):
return [l[0]-1] + recurse2(l[1:]) if l else []
def recurse3(l):
if len(l) == 0:
return []
else:
return [l[0] -1] + recurse3(l[1:])
def recurse4(l, x = []):
if len(l) == 0:
return []
else:
x.append(l[0] -1)
recurse4(l[1:], x)
return x
Here's a recursive solution that can cope with large lists without hitting the recursion depth limit. By using divide and conquer the recursion depth is O(log(N)) at worst, compared to O(N) with naive recursion. Any sort of recursion is a poor choice of technique for this problem though, as it's trivially solved with a simple for-loop.
def dec_list(xs, a, b):
if b == a + 1:
xs[a] -= 1
if a + 1 >= b: return
mid = (a + b) // 2
dec_list(xs, a, mid)
dec_list(xs, mid, b)
def dec(xs):
dec_list(xs, 0, len(xs))
xs = range(1001)
dec(xs)
print xs
