What changes should I make to my existent code in order to make it a recursive function?-CodePudding

I'm trying to write up a code that will return all even numbers first and then the odd numbers will be appended at the end of the list (order doesn't matter), and I successfully did this with the helpof some Stack Overflow users.. However, I'm wondering that is there a way I can do this recursively??

Here is the original code

def evenorodd(s):
    evens = []
    odds = []
    for num in s:
        if num%2 == 0:
            evens.append(num)
        else:
            odds.append(num)
    return evens   odds
print(evenorodd([1,2,3,4,5,6,7,8]))

This function works just fine, but to broaden my understanding of recursive functions, can someone please help change this code into a recursive one so I can get an idea of what I should do to make it recursive?

CodePudding user response：

Consider the following. We need an exit condition from the recursion: when the list is empty. We have an accumulator we pass from one iteration to the next, which is a tuple of two lists: one for evens, one for odds.

Each time we call the function if the list is empty, we concatenate those two lists and return the resulting list.

If the list is _not_empty, we name the parts of the list first and rest for easier reference. If first is even, we concat it onto the first list in the accumulator and call odd_or_even with the rest of the list and the updated accumulator. If it's odd, we do the same but we modify the accumulator accordingly.

>>> def odd_or_even(lst, acc=([], [])):
...     if lst == []:
...         return acc[0]   acc[1]
...     else:
...         first = lst[0]
...         rest = lst[1:]
...         if first % 2 == 0:
...             return odd_or_even(rest, (acc[0]   [first], acc[1]))
...         else:
...             return odd_or_even(rest, (acc[0], acc[1]   [first]))
... 
>>> odd_or_even([1, 2, 3, 4, 5])
[2, 4, 1, 3, 5]
>>>

If you learn a functional programming language like OCaml, SML, or Haskell, you'll see a lot of logic like this. It's much less common in the likes of Python or Ruby.

CodePudding user response：

Inserting evens at the front and odds at the end:

def evenorodd(s):
    if not s:
        return []
    tmp = evenorodd(s[1:])
    tmp.insert(s[0] % 2 * len(tmp), s[0])
    return tmp

More efficient version:

def evenorodd(s):
    s = iter(s)
    for x in s:
        tmp = evenorodd(s)
        tmp.insert(x % 2 * len(tmp), x)
        return tmp
    return []

CodePudding user response：

Your recursive version could build the left (even) and right(odd) sides of the result by passing itelf two lists that it eventually concatenates for the final result:

def evenorodd(s,e=[],o=[]):
    return evenorodd(s[1:], e s[:1-s[0]%2], o s[:s[0]%2]) if s else e o

s = [1,2,3,4,5,6,7,8]
print(evenorodd(s))
[2, 4, 6, 8, 1, 3, 5, 7]

CodePudding user response：

I so don’t recommend this, but it was fun. It uses an accumulator, evens, to collect all the even values while emitting all the odds.

def evenorodd(s):
    def inner(s, odds):
        if not s:
            return odds
        
        num = s[0]
        if num % 2 == 0:
            return [num]   inner(s[1:], odds)
        return []   inner(s[1:], odds   [num])

    return inner(s, [])

print(evenorodd([1,2,3,4,5,6,7,8]))

It’s weird, but only examines each value once.

Edit: As a bonus, here’s the same thing in Lisp.

(define inner (s evens)
    (if (null? s)
        evens
        (if (eq (modulo (car s) 2) 1)
            (cons (car s) (inner (cdr s) evens))
            (inner (cdr s) (append evens (list (car s)))))))

(define evenorodd(s)
    (inner s '()))

(print (evenorodd '(1 2 3 4 5 6 7 8)))

I just got a Lisp editor on my iPad and wanted to play with it, so there you go.