0

Hey guys I am not good with recursion function problems. Can someone tell me a good source to learn about that and also in this problem I do not understand how is the recursion working? It would be great if someone can explain this situation.

items = [6, 20, 8, 19, 56, 23, 87, 41, 49, 53]


def find_max(items):
    if len(items) == 1:
        return items[0]

    op1 = items[0]
    # print(op1)
    op2 = find_max(items[1:])
    # print(op1, op2)

    if op1 > op2:
        return op1
    else:
        return op2


print(find_max(items))
Improve this question

3 Answers 3

Reset to default
1

At 1st iteration, the list containing [6, 20, 8, 19, 56, 23, 87, 41, 49, 53] it takes the element 6 and put it in op1. Then, it calls for the function once again, this time with the list [20, 8, 19, 56, 23, 87, 41, 49, 53] without the first element, and put the maximum of it in op2. Let's assume the recursion works, so it really gives you the maximum of the list [20, 8, 19, 56, 23, 87, 41, 49, 53] in op2. So the maximum of the list is the maximum between op1 and op2.

What we did here? We took our big problem (find the maximum) and divide it into smaller part: let's find the maximum between 6 and the maximum of the smaller list. Then you apply this step over and over, until the list is left with only one element - which is the maximum. That is one way to use recursion, divide and conquer.

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

Comments

0

you are in good company when you struggle with recursion. Recursion in computer science means, that a function calls itself.

To explain it, I will start with a more easy function:

items = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
def add_list(items):
    if len(items) == 1:
        return items[0]
    op1 = items[0]
    op2 = add_list(items[1:])
    return op2 + op1;

print(add_list(items))

This function shall add all elements of the list called "items". The term op1 = items[0] assignes the first list item to op1. After that the function calls itself (the recursion) with a reduced set of list items namely items without 1. The term items[1:] cuts of the first item which results in [2, 3, 4, 5, 6, 7, 8, 9, 10]. The procedure is waiting here until the recursive call finishes. You can assume this as a new function instance of add_list is called. Now the same procedure begins again with the reduced list. This goes on until the list only contains one element. Then the magic happens. The whole recursion chain rolls back. The term 

if len(items) == 1:
   return items[0]

is hit. The last recursion call returns the last item of the list items. Now the chain returns to the former call of add_list. op2 gets the last item of items, here 10. This chain element will return (10 + 9). Then the recursion rolls back to the former layer and op2 will get the value (10 + 9). This chain element will return (10 + 9) + 8; And so on.

The same happens to the function find_max. But instead of summing the values the chain of recursion will return the highest value by :

if op1 > op2:
   return op1
else:
   return op2

instead of return op2 + op1.

Improve this answer

Comments

0

Each time the function calls itself it takes the first item from the list and places it into op1 then passes the rest of the list to the next recursion. Note that this happens before the function returns and before it actually makes any attempt to find the maxinum. Each recursion only runs as far as this line before the next one starts.

op2 = find_max(items[1:])

This continues until you the list has only one item left, all the other items in the list are assigned to different versions of op1, one in each of the layers of recursion. When the list is only one item long, the last function you called is the first to return.

if len(items) == 1:
    return items[0]

The next one down can then proceed to actually run the comparison part of the code:

if op1 > op2:
   return op1
else:
   return op2

What happens next is that the functions all return in the reverse of the order they were called, each time deciding whether to keep their local value of op1 or the return value from the previous recursion, op2. Once all the functions return you are left with the highest item.

This is not a great way to do recursion as it means you have a 'stack' of functions all waiting to return at the same time. The longer the list, the deeper the stack. Eventually you will either reach the max recursion depth of the interpreter or run out of memory. The better approach is called tail-recursion, however I'm not sure the Python interpreter actually supports this so there may not be anything to be gained by changing anything.

Improve this answer

4 Comments

Thank you very much now I understand it fully. Can you please recommend me the alternative ways of recursion since they have a drawback of running out of memory.
I edited the answer a little. I don't think Python actually supports any better form of recursion. I was thinking of languages like Scala which are designed around recursion.
No worries, consider upvoting the answer if it helped you.
I would love to but my score is still at the 13 and it would not let me do it before 15 or more. But don't worry I will keep that in mind.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.