재귀 이해에 혼란이 있음

Question

다음 코드 과 약간 혼동되어 트리의 높이와 sum of n nos을 재귀 적으로 찾는 코드가 아래에 있습니다. 재귀 횟수에 따라 lheight과 rheight이 저장하는 항목은 무엇입니까? '

int findSum(int n){ 
    int sum; 
    if(n <= 0) return 0; 
    else sum = findSum(n-1); // here 
    return sum; 
} 

그것은 않는 이유 0으로 출력을 인쇄 : I가 변경할 경우

int findSum(int n){ 
    int sum; 
    if(n <= 0) return 0; 
    else sum = n + findSum(n-1); 
    return sum; 
} 

: 여기

int height(struct node* node) 
{ 
    if (node==NULL) 
     return 0; 
    else 
    { 
    lheight = height(node->left); 
    rheight = height(node->right); 
    if (lheight > rheight) 
     return(lheight+1); 
    else return(rheight+1);  
    } 
} 

하나 이상의 설명은, 그것이 n nos의 합 출력 인 위의 트리 코드가 수행하는 경우 재귀의 수를 반환합니다. 당신이 다음

sum = 1 + findSum(n-1); 

lheight를 사용하는 두 번째 재귀 재귀의 수를 반환 할 것을 원하고 있기 때문에 재귀 트리 레벨을 반환 rheight 경우

Answer 1

두 번째 재귀

sum = findSum(n-1) = findSum(n-2) = findSum(n-3) = ..... = findSum(0) = 0; 

에 해당 함수에는 두 변수에 대해 이라는 증분이 있습니다.

당신은 당신의 findsum() 당신이 당신의 findsum() 함수의 끝에서 sum+1하지 sum를 반환해야합니다 귀하의 height() recusrsion로 samething을 원하는 경우 :

int findSum(int n){ 
    int sum; 
    if(n <= 0) return 0; 
    else sum = findSum(n-1); 
    return sum+1; //<<<<< should return sum +1 as you did in the height function 
} 

return sum+1;이 평가됩니다 만

findSum(n-1) 경우 ; findSum(n-2); findSum(n-3); ... findSum(0); 호출됩니다. findSum(0)가 호출 될 때

• , 그것은 0를 반환합니다;
• findSum(1)이 호출되면 (그래서 sum = 0)을 실행 한 다음 sum+1 (1)을 반환합니다.
• findSum(2)을 호출하면 sum=findSum(1) (그래서 sum = 1)을 실행 한 다음 sum+1 (2)을 반환합니다.
• findSum(3)이 호출되면 sum=findSum(2) (그래서 sum = 2)을 실행 한 다음 sum+1 (3)을 반환합니다.
• .
• .
• .findSum(n)가 호출 될 때
• , 그것은 (n)를 sum=findSum(n-1) (그래서 sum = n-1)을 실행하고 sum+1를 반환한다;

Answer 2

저는 이것을 종이에 제안합니다. 우리가 (수정되지 않은) findSum 기능을 위해 그것을 할 경우는 다음과 같이 될 것입니다 :

까 하나이다 당신이 다음 단계로 읽

findSum(2); 

과 같이 호출 말 :

1: sum = 2 + findSum(2 - 1); 

어떤 findSum(1)를 호출합니다

2: sum = 1 + findSum(1 - 1); 

전화에 이르게 의 findSum(0)

3: return 0; 

인 이제 우리는 2 다시 한 단계 올라가 :

2: sum = 1 + 0; 

한 번 백업 더 :

이

1: sum = 2 + 1 

그래서 findSum(2)의 결과가 3

입니다

Answer 3

높이와 높이는 왼쪽 하위의 높이에 불과합니다. 트리 및 트리의 특정 레벨에서 오른쪽 하위 트리 resp.

예를 들어 보면 이해하기가 더 쉽습니다.

첨부 된 그림에서 루트 F부터 시작합니다. 루트가 null인지 아닌지 확인하고 그렇지 않은 경우 오른쪽 하위 트리와 왼쪽 하위 트리의 높이를 찾습니다. 우리는 그것에 하나 더 추가하고 돌아옵니다. 이것이 우리가 수동으로하는 방법입니다.

이제 왼쪽 하위 트리의 높이를 찾는 동안 우리는 널 포인터에 도달 할 때까지 반복적으로 내려갑니다.이 지점에서 우리는 0을 반환합니다. 따라서 A에 대한 값 반환은 0이고, 그런 다음 오른쪽 높이를 확인합니다 서브 트리 (즉, D)에 대해 그리고 C에 0을 반환 할 때까지 재귀 적으로 내려 가고 0과 마찬가지로 0을 반환합니다. C와 E의 최대 값에 1을 더하고 (즉 0) 수평. 이제 우리는 A에 대해 값 0을 가지며 D에 대해 1을가집니다. 우리는 max (즉, 1)에 하나를 더하고 상위 레벨에 그것을 반환합니다. 마찬가지로 전체 트리의 왼쪽 하위 트리의 높이입니다. 마찬가지로 오른쪽 하위 트리의 높이가 계산됩니다.