CODEWITHSUNDEEP
pythonrecursionquadtree
Sounak
Sounak

Reputation: 4968

find area of a square recursively

I have a big square, which is made of small square-tiles of fixed size.

The area of these small square-tiles are known.

enter image description here

One of the tile is shown on the upper left corner.

Now,

Each square can be broken down into 4 subsquares. And each square has a key which identifies the square.

There might be many empty squares inside the big-square. In those cases the key doesn't exist and the area is considered as zero.

enter image description here

The smallest tile have a key length of 3.

I want to recursively find the area of any square given a key.

This is what I am trying. But it is not giving me the right solution.

findAreaRecursive(self, key, maxDepth=3):
    if len(Key) == maxDepth:
        if self.keyExists(key):
           return self.getAreaValue(key)
        else:
           return 0

    else:


        keyChild0 = key + '0'
        keyChild1 = key + '1'
        keyChild2 = key + '2'
        keyChild3 = key + '3'

        if self.keyExists(keyChild0): 
            areaChild0 = self.findAreaRecursive(keyChild0, maxDepth)
        else:
            areaChild0 = 0

        if self.keyExists(keyChild1): 
            areaChild1 = self.findAreaRecursive(keyChild1, maxDepth)
        else:
            areaChild1 = 0

        if self.keyExists(keyChild2): 
            areaChild2 = self.findAreaRecursive(keyChild2, maxDepth)
        else:
            areaChild2 = 0

        if self.keyExists(keyChild3): 
            areaChild3 = self.findAreaRecursive(keyChild3, maxDepth)
        else:
            areaChild3 = 0

        return areaChild0 + areaChild1 + areaChild2 + areaChild3

What am I doing wrong. I am new to recursion. Any help is welcome.

Upvotes: 0

Views: 1603

Answers (1)

J Richard Snape
J Richard Snape

Reputation: 20344

It seems to me that your recursive finder is a little over complicated. You are kind of half unrolling the recursion within the function. The following is an example that is maybe a little more 'purely' recursive. It works if I assume that keyExists() works by returning true if there is an area value for the key.

def findAreaRecursive(self, key, maxDepth=3):
    totArea = 0
    if len(key) == maxDepth:
        if self.keyExists(key):
           totArea += self.getAreaValue(key)
    else:
        for i in range(4):
            newKey = key + str(i)
            totArea += findAreaRecursive(self, newKey, maxDepth)

    return totArea

However....

Recursion can be difficult to get your head around. If you want to keep pursuing your approach, you can help clarify your question by

  1. putting in the whole code - including getAreaValue() and keyExists() function and we can have a look at it to work out the execution path and what is failing. For example, you we can't see the logic for your keyExists() function, maybe that is sometimes giving the wrong value, resulting in one branch of your code returning a zero when you don't expect it.

  2. putting in a few print statements in the recursion (OK as the recursion isn't too deep in your case). You'll see what's happening. I'd start with a print statement as the first in the function saying

    print "Called with key",key

    which will allow you to follow which keys are being called and you can check whether it's happening in the order you expect.

EDIT:

See also this answer to a similar question which begins with a really nice summary of a way to think of recursion as you say you are new to recursion.

Upvotes: 2

Related Questions