이진 트리에서 재귀 이해하기

Question

안녕하세요 저는 학교에서 프로그래밍을 처음 사용하여 재귀 및 이진 트리를 학습하고 있습니다. 그러나 재귀는 내 마음을 정말로 녹여줍니다.

그래서 출력에 선주문 형식

def preorder(self, preorder_list): 
    """ (BinaryTree) -> list 
    Return a list of the items in this tree using a *preorder* traversal. 
    """ 

    if self.root is not EmptyValue: 
     if self.left and self.right != None: 
      preorder_list.append(self.left.preorder(preorder_list)) 
      preorder_list.append(self.right.preorder(preorder_list)) 

def helper_preorder(self): 
    preorder_list = [] 
    self.preorder(preorder_list) 

    return preorder_list 

을 시도 이진 트리에 재귀 함수를 시도했다 내가 얻을 출력이이 코드를 실행하면 :

예를 들어

;

[None, None, None, None] 

이제 재귀 추론에 문제가 있다고 생각됩니다. 그래서 나는 재귀 적 추론의 문제가 무엇인지, 어떻게 재귀에서 자기 자신을 더 잘할 수 있는지 알고 싶다. 시간에 대한

감사합니다.

Answer 1

preorder에서 아무것도 반환하지 않으며 파이썬이 암시 적으로 None을 반환한다는 것이 문제입니다. 따라서 함수의 반환 값을 목록에 추가하지만 값은 None입니다. 함수는 다음과 같이한다 (의사 코드에서 유효하지 파이썬) ¹ : 그것 때문에 당신이 최적화 할 수 있도록 내가 return 문을 복제하고

preorder(node, list): 
    if node is Empty: 
     return list 
    else: 
     new_list.append(node.data) 
     preorder(node.left, new_list); 
     preorder(node.right, new_list); 
     return list 

참고,하지만 난이 방법을 설정 재귀 호출을 기본 사례 또는 재귀 호출로 생각하면 재귀를 쉽게 이해할 수 있습니다.

재귀를 이해하려면 , 작고 쉬운 문제로 어려운 문제를 해결하는 방법에 대해 생각해보십시오. 간단한 재귀 예제 중 하나 인 간단한 예제를 보겠습니다 : factorial(n).

무엇이 factorial(n)입니까? 정말 대답하기 어려운 질문입니다. 그래서 더 간단한 것을 찾아 보겠습니다.

수학 수업에서 우리는 n! = n*(n-1)*(n-2)*...*(2)*(1)을 알고 있으므로 여기서 시작하겠습니다. 우리는 바로 n! = n * (n-1)!을 볼 수 있습니다. 도움이된다. 이제 우리의 계승 함수의 시작을 쓸 수 있습니다 :

factorial(n): 
    return n * factorial(n-1) 

아직 완료되지 않았습니다. 우리가 그것을 실행하면 영원히 갈 것이고 멈추지 않을 것입니다 . 그래서 우리는 기본 케이스라고 불리는 것을 필요로합니다 : 재귀를위한 정지 지점. 문제가 너무 단순해서 우리가 답을 안다.

다행히도 자연의 기본 사례는 1! = 1이며, 이는 사실입니다. 그래서 우리는 우리의 기능에 추가

factorial(n): 
    if n == 1: return 1 
    else return n * factorial(n) 

는 그냥 어떻게 작동이 명확의 작은 뭔가를 추적 할 수 있도록하기 위해, n=4을 말한다.

factorial(4)입니다. 분명히 4 != 1이므로 factorial(4) = 4*factorial(3)입니다. 이제 우리는 재귀에 대한 아름다운 점인 과정을 반복합니다. 원래의 문제의 더 작은 부분 집합에 동일한 알고리즘을 적용하고 그 부분으로부터 솔루션을 구축합니다.

우리의 추적은 다음과 같은 :

factorial(4) = 4*factorial(3) 
factorial(4) = 4*3*factorial(2) 
factorial(4) = 4*3*2*factorial(1) 

을 이제, 우리는 factorial(1)는 것을 알고 : 그냥 1, 우리의 기본 케이스입니다. 그래서 결국 우리는이 단지 하나의 가능한 방법입니다

factorial(4) = 4*3*2*1 
factorial(4) = 24 

---

¹있다; 거기에 다른 사람이있다, 그러나 이것은 내가 그 자리
² 먼저 재귀를 이해해야에 해낸 것입니다 (죄송합니다, 나는 저항 할 수 없었다) 현실 세계에서
³, 그것은 결국 중지 : 때문에 각각의 재귀 호출은 함수 매개 변수와 지역 변수 등을 추적하기 위해 일부 메모리를 사용하며, 무한대로 반복되는 코드는 결국 할당 된 메모리를 초과하고 충돌 할 것입니다. 이것은 스택 오버플로 오류의 가장 일반적인 원인 중 하나입니다.