Inversing a list recursively

Question

I created a function that will inverse a list recursively but it uses an global list in witch it puts the elements. Can this be rewritten so that it won't use an outside variable/list to achieve the same result.

Here is the code:

invs = []

def inv_list(list_, elem):
    global invs

    if elem is not None:
        invs.append(elem) 

    if not list_:
        return invs

    else:
        try:
            el = list_.pop()
            inv_list(list_, el)

        except Exception:
            pass

use the list as an arg – Padraic Cunningham Jun 22 '15 at 21:30 — Padraic Cunningham, Jun 22 '15 at 21:30
Why not just use the `reverse()` method? – uname01 Jun 22 '15 at 22:02 — uname01, Jun 22 '15 at 22:02

Emanuele Paolini · Answer 1 · 2015-06-22T21:37:09.777

2

What about:

def inv_list(lst):
    if not lst:
        return []
    return inv_list(lst[1:]) + lst[:1]

edited Jun 22 '15 at 21:37

answered Jun 22 '15 at 21:24

Emanuele Paolini

9,912
3
38
64

Or `return lst if not lst else lst[-1:] + inv_list(lst[:-1])` – Padraic Cunningham Jun 22 '15 at 21:29
@PadraicCunningham I like the idea of using lst[-1:] instead of [lst[-1]] (stolen!). Instead I think it is correct to return a copy of the empty list instead of the original lst when lst is empty. Otherwise you have an inconsistent behavior – Emanuele Paolini Jun 22 '15 at 21:38
yep, you can also `return [] if not lst else lst[-1:] + inv_list(lst[:-1])` – Padraic Cunningham Jun 22 '15 at 21:42

score 0 · Answer 2 · answered Jun 22 '15 at 21:25

0

it looks like you are doing a whole lot more work than you need to

def reverse_recurse(a_list):
    if not a_list:
        return []
    return [a_list.pop(),] + reverse_recurse(a_list)

answered Jun 22 '15 at 21:25

Joran Beasley

110,522
12
160
179

score 0 · Answer 3 · answered Jun 22 '15 at 21:30

While your implementation could be improved in various ways, when I find that I want to build something recursive without using globals and without making the interface feel dirty is create a nested helper function:

def inv_list(list_):
    invs = []

    def helper(elem):
        if elem is not None:
            invs.append(elem) 

        if not list_:
            return invs
        else:
            try:
                el = list_.pop()
                return helper(el)
            except Exception:
                pass

    return helper(None)

That way, you can have values that are at the scope of the outer function.

Ericson Willians · Answer 4 · 2015-06-22T22:20:39.450

The problematic way to do it is simple, just use default arguments.

def rec_reverse(input=[], output=[]):
    if len(input) == 0:
        return
    else:
        output.append(input.pop())
        rec_reverse(input, output)
        return output

x = list(range(10))
y = list(range(20))
print(rec_reverse(x, []))
print(rec_reverse(y, []))

Just remember to pass a new list to the output, so that you can call it again without getting old values.

Nevertheless, you can use the safe approach without using default arguments:

def rec_reverse(input):
    if not input:
        return input
    else:
        return [input.pop(), ] + rec_reverse(input)

And you can also use its recursive equivalent as a lambda expression:

rec_reverse = lambda input=[]: [] if not input else [input.pop(), ] + rec_reverse(input)

Keep in mind though, that there's an even simpler solution without using recursion at all:

x = list(range(10))
rec_reverse = lambda input: input[::-1]
print(rec_reverse(x))

Since in Python, you can reverse any list using extended slice notation.

Also, you can just use reverse() and spare you the trouble.

def reverse(input):
    input.reverse()
    return input

It's worth pointing out that using a list as a default function argument is problematic as you will get back the same instance each time the default arg is used. Try calling your function twice. — FatalError, Jun 22 '15 at 21:36

Kevin Ward · Answer 5 · 2015-06-23T20:02:12.050

Building on Rederick Deathwill, here is a simplified version of your function:

def inv_list(list_):
    def inner(list_, invs):
        if not list_:
            return invs
        else:
            invs.append(list_.pop())
            return inner(list_, invs)

    return inner(list_, [])

It uses a default value for invs, getting rid of the need for a global variable to hold the inverted list. With subsequent invocation, invs is passed along so that the next call can build on it.

Once the bottom of the call stack is reached, the function returns the reversed list. A nice addition to the original is the return inner(list_, invs) line, which allows the caller to capture the new list as the return value.

This is not the shortest, but I think it is at least readable.

Inversing a list recursively

5 Answers5