How to solve Index Error in recursive function?

Question

I have some problems when I write the recursive function.

The problem is finding the maximum total value in binary tree.

And each node can choose maximum child node.

For example, Node 8 can choose 1 and 0, then add 1.

My code is here,

triangle = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
#result = 30
depth = 1
answer = triangle[0][0] # depth : 0
total = 0

N1,N2 = triangle[1][0], triangle[1][1]

And, I write Recursive Functions like this,

def min_max(depth, N, total):
    if depth == len(triangle):
        return total
    else:
        a,b = triangle[depth+1][triangle[depth].index(N)], triangle[depth+1][triangle[depth].index(N)+1]
        total += max(a,b)
        N = max(a,b)
        return min_max(depth+1, N, total)

min_max(depth, N1, total)

But, I got list index out of range.

How can I fix recursive function?

Just add a in the if condition if depth+1 == len(triangle) and you will not crash, but not sure if other logic is correct. — Ilian Zapryanov
– Ilian Zapryanov, Commented Jun 6, 2022 at 16:31

Ram · Accepted Answer · 2022-06-06 18:29:02Z

When you write the binary tree into python list, depth becomes index of the list. index of list always starts from 0 where as length starts from 1.(i.e list of length 5 will be having indexes ranging from 0 to 4)

So, the starting depth should be equal to 0 and the terminal condition of the recursive function should be if depth+1 == len(triangle)

Point 1 removes the index out of range issue. However we still have the problem with logic of code.

total += max(a,b) is checking for the maximum of the two number where as it should be looking out for maximum value of two binary tree.

Above code will parse through the single line of data with maximum values and ignores rest of the possibilities.

Below is an alternate possibility to code.

def reduce(triangle: "list[list]"):
    print(triangle, flush=True)
    print('-----------------------------------', flush=True)
    if len(triangle) == 1:
        return triangle[0][0]
    else:
        last_line = triangle.pop()
        position = 0
        for value in triangle[-1]:
            value += max(last_line[position], last_line[position + 1])
            triangle[-1][position] = value
            position += 1
        return reduce(triangle)

print(reduce(triangle))

It works by removing the last line and adding maximum possible value to the second to last line each iteration until only one line remains

Output:

[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
-----------------------------------
[[7], [3, 8], [8, 1, 0], [7, 12, 10, 10]]
-----------------------------------
[[7], [3, 8], [20, 13, 10]]
-----------------------------------
[[7], [23, 21]]
-----------------------------------
[[30]]
-----------------------------------
30

Collectives™ on Stack Overflow

How to solve Index Error in recursive function?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related