재귀 적으로 사각형의 면적을 찾으십시오

Question

나는 고정 된 크기의 작은 사각형 타일로 만들어진 커다란 사각형을 가지고 있습니다.

이 작은 정사각형 타일의 면적은 알려져 있습니다. 타일의

한

은 왼쪽 상단에 표시됩니다.

지금,

각 사각형은 4 개의 부분 집합으로 나눌 수 있습니다. 각 사각형에는 사각형을 나타내는 키가 있습니다.

큰 사각형 안에 빈 사각형이 많이있을 수 있습니다. 이 경우 키는 존재하지 않으며 영역은 0으로 간주됩니다.

작은 타일은 내가 재귀 적으로 키 주어진 임의의 사각형의 영역을 찾으려 3.

의 키 길이를 갖는다.

이것은 내가 시도한 것입니다. 그러나 그것은 나에게 올바른 해결책을주지 못하고있다.

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 

내가 뭘 잘못하고있어. 나는 재귀가 처음이다. 어떤 도움도 환영합니다.

Answer 1

재귀 파인더가 조금 복잡해 보입니다. 당신은 함수 안에서 재귀를 절반 언 롤링하고 있습니다. 다음은 좀 더 순전히 재귀적인 예입니다. keyExists()가 키의 영역 값이 있으면 true를 반환한다고 가정하면 작동합니다. 재귀 주위에 당신의 머리를 얻기 어려울 수 있습니다

그러나

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 

.... 당신이 당신의 접근 방식을 추구하고 유지하려면

1. 전체 코드를 넣어 질문을 명확히 도움이 될 수 있습니다 - getAreaValue()와 keyExists (포함) 기능을하고는 밖으로 작업에서 우리는 모양을 가질 수있다 실행 경로 및 실패한 부분 예를 들어, keyExists() 함수에 대한 논리를 볼 수 없으면 잘못된 값을 제공하여 예상치 못한 경우 코드의 한 분기에서 0을 반환 할 수 있습니다.

2. 재귀에 몇 개의 print 문을 넣습니다 (재귀가 너무 복잡하지 않으므로 확인하십시오). 무슨 일이 일어나는지 보자. 함수의 첫 번째는 당신이 키가 호출되고있는 수행 할 수

   print "Called with key",key 
   

   의 말 나는 인쇄 문으로 시작 했죠 그리고 당신이 기대하는 순서에서 일어나고 여부를 확인할 수 있습니다.

편집 :

당신이 재귀를 처음 말한대로 재귀 생각하는 방법의 정말 좋은 요약로 시작하는 비슷한 질문에도 this answer를 참조하십시오.