Trouble converting for loop into recursive function in python

Question

I am trying to write a program that finds the max sum of nonadjacent elements in a 1 dimensional array and so far I have this:

def find_max_sum(arr):
    incl = 0
    excl = 0

    for i in arr:

        # Current max excluding i 
        new_excl = excl if excl>incl else incl

        # Current max including i
        incl = excl + i
        excl = new_excl

    # return max of incl and excl
    return (excl if excl>incl else incl)

It works. My only question is how would one go about transforming this function into a recursive function without using the for loops? My brain can't seem to find a way to do this.

Can you attempt to rephrase the problem you're working on? Regardless of the specifics, likely what you'll want to do is have find_max_sum(arr) call find_max_sum(arr[1:]) or find_max_sum(arr[:-2]) (so, shrink the size of the array by some amount in each step, likely one), with a base case of an array of size 1. — Mark Schultz-Wu
– Mark Schultz-Wu, Commented Mar 14, 2017 at 8:33

Elmex80s · Accepted Answer · 2017-03-14 11:26:09Z

2

Step 1: rewrite your function so it is more Pythonic

def find_max_sum(lst):
    incl, excl = 0, 0

    for i in lst:
        incl, excl = excl + i, max(excl, incl)

    return max(excl, incl)

Step 2: now it is easy to rewrite it to a recursive function

def find_max_sum_recursive(lst, incl, excl):        
    if len(lst) > 0:
        i = lst[0]
        incl, excl = excl + i, max(excl, incl)

        return find_max_sum_recursive(lst[1:], incl, excl)
    else:
        return incl, excl

def call_find_max_sum_recursive(lst):
    return max(find_max_sum_recursive(lst, 0, 0))

Now you call

>>> call_find_max_sum_recursive([1, 2, 10, 3, 4])
15

Step 1 is not absolutely necessary. After all it is about the block of code in your for i in arr: and how they affect incl and excl. However it might help you rewriting.

edited Mar 14, 2017 at 11:26

answered Mar 14, 2017 at 8:55

Elmex80s

3,5041 gold badge17 silver badges25 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

VPfB Over a year ago

Using a tuple in the parameter list is not supported in Python3 (PEP 3113).

Elmex80s Over a year ago

@VPfB Thanks, I fixed it.

PM 2Ring Over a year ago

FWIW, here's a one-liner version of the Python 3 version: def find_max_sum_recursive(lst, t): return find_max_sum_recursive(lst[1:], (lst[0] + t[1], max(*t))) if lst else t. It's generally considered more Pythonic to do if lst: than if len(lst) > 0:; OTOH, your version has the advantage that it will complain in the if statement if lst isn't an indexable collection.

Elmex80s Over a year ago

@PM2Ring thanks for your feedback. However I disagree about if lst: to be prefered over if len(lst) > 0.

PM 2Ring Over a year ago

Fair enough. But I did say that your version does have an advantage. :) Actually, my statement wasn't quite correct: I should've said that yours will complain in the if statement if lst doesn't have a length, since there are many objects that have a well-defined length but which aren't indexable (eg sets).

Collectives™ on Stack Overflow

Trouble converting for loop into recursive function in python

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related