CODEWITHSUNDEEP
pythonrecursion
Jonatan
Jonatan

Reputation: 61

Recursion in lists

def obsah(myList):
    def recursion(myList,deep=1,result=(None)):
        if type(myList) == list:
            for i in range(len(myList)):
                if type(myList[i]) == list:
                    deep+=1
                    recursion(myList[i],deep,result)
                else:
                    result = (deep,myList[i])
                    break
        else:
            result = (0,myList)
        return result
    return recursion(myList)

this function is supposed to return the dept of recursion and the value of last element in list as tuple:

 obsah(['a'])
(1, 'a')
>>> obsah([[123]])
(2, 123)
>>> obsah([[[[[(3,7)]]]]])
(5, (3, 7))
>>> obsah(3.14)
(0, 3.14)
>>> obsah([[[1],2]])
(1, None)

instead the outputs are:

(1, 'a')
None
None
(0, 3.14)
None

After several times of testing i found that my temporary result is good but, the recursion is going one more time with default parameter(none), where is the problem ? shouldn't it end with that returns ?

Upvotes: 2

Views: 110

Answers (2)

Łukasz Rogalski
Łukasz Rogalski

Reputation: 23203

Simpler solution using while loop:

def obsah(nested):
    depth = 0
    while isinstance(nested, list) and len(nested) == 1:
        nested = nested[0]
        depth += 1
    return depth, None if isinstance(nested, list) else nested

print obsah(['a'])
print obsah([[123]])
print obsah([[[[[(3,7)]]]]])
print obsah(3.14)
print obsah([[[1],2]])

Prints:

(1, 'a')
(2, 123)
(5, (3, 7))
(0, 3.14)
(1, None)

This big if in return is purely for special case, that tells me it's something wrong either with approach or problem definition.

Upvotes: 1

Bill Lynch
Bill Lynch

Reputation: 81916

First, an aside:

Instead of writing this:

for i in range(len(myList)):
    myList[i]

Write this:

for element in myList:

Or, if necessary:

for i, element in enumerate(myList):

Now then, your code...

When we write a recursive function, we want to talk very explicitly about two types of cases. The base case, and the recursive case. We should be able to model them in our code as that style very explicitly.

In your code, you really don't follow that model. I can't really find the base case. Let's talk about the base cases:

  1. If the object passed to the recursive function is not of type list, then we return the current depth and the object passed in.
  2. If the list passed to the recursive function does not have a length of 1, then we return the current depth and None.

And our recursive case is to increment the depth and pass myList[0] to the recursive call.

So your code should be fairly straightforward:

def obsah(myList):
    return recursion(myList)

def recursion(myList, depth=0):
    # Base Case
    if type(myList) != list:
        return (depth, myList)

    # Another Base Case:
    if len(myList) != 1:
        return (depth, None)

    # Iterative case
    return recursion(myList[0], depth+1)

print obsah(['a'])
print obsah([[123]])
print obsah([[[[[(3,7)]]]]])
print obsah(3.14)
print obsah([[[1],2]])

Which outputs:

(1, 'a')
(2, 123)
(5, (3, 7))
(0, 3.14)
(1, None)

Remember:

The key thing here is to write down the base case(s) and the recursive case before you start writing actual code.

Upvotes: 2

Related Questions