사실 이거 아주 간단한 알고리듬인데…리커시브를 쓰는것들은 프로그램 자체는 구현이 아주 간단해지지만 머릿속으로 쫒아가며 이해하기는 항상 헷갈리네요. 예를들어 트리를 인서트해주고 그 입력된 투리의 하이트를 구하는 일반적인 함수는
int tree_height(Node* root) {
// Get the height of the tree
if (!root)
return 0;
else {
// Find the height of both subtrees
// and use the larger one
int left_height = tree_height(root->left);
int right_height = tree_height(root->right);
if (left_height >= right_height)
return left_height + 1;
else
return right_height + 1;
}
}

이런식인데… 이해가 잘 안가요. 이해가 안가는 이유는 이게 결국 리커시브가 되면서 결국 마지막 리프에서 레프트와 라이프 포인터가 널포인터가 될것이고 (왜냐하면 인서트 할때 마지막 리프들의 레프트/라이트 포인터들은 널포인터로 채워지니까) 결국 리턴값이 “항상” 0 로 끝날것같은 “착각”이 계속 드는데…. 이 “착각”이 왜 잘못된건지 어디서잘못된건지 잡아내기가 힘들군요. (더 이상한건 프린트해보니…루트에서 리프들쪽으로가 아니라 리프쪽에서 루트쪽으로 리커시브 프로시줘가 이루어지는 듯한 아웃풋이..)

// find 주석 이후 부분을
return max(tree_height(root->left), tree_height(root->right)) + 1;
처럼 간략화해서 보면 해석하기에 어떠실까요?

그 간략화도 머리속 혼동을 해결하기에 도움이 안되는거 같아요. 하나하나 노드를 따라가며 프린트를 해봐야 할지…그래도 아직 의문만 더 생기는군요.

A
/ \
B C
/
D

tree_height(A)
tree_height(A->left) // B
tree_height(B->left) // NULL
return 0 // B->left
tree_height(B->right) // NULL
return 0 // B->right
return 0+1 // A->left
tree_height(A->right) // C
tree_height(C->left) // D
tree_height(D->left) // NULL
return 0 // D->left
tree_height(D->right) // NULL
return 0 // D->right
return 0+1 // C->left
tree_height(C->right) // NULL
return 0 // C->right
return 0+1+1 // A->right
return 0+1+1+1 // A

Indent로 recursive call의 depth를 표현해보았고, tree_height 호출과 return을 시간 순서대로 적어보았습니다. 이렇게 보시면 이해하기에 어떠실지요?

이걸 제 머리가 잘 못따라 가는거 같네요.

return 0 // B->left
tree_height(B->right) // NULL
이런 부분에서 브레이크가 걸리네요.

그리고
return 0+1 // A->left
에서 A->left 의 합이 1로 sum이 되어 왜 계속 “저장”이 되는지도 이해가 안가고요. return (sum+1) 부분이 계속 왜 “합해져서 누적”되는지 그 부분이 감이 잘 안오는듯해요.
return 0+1+1 // A->right
return 0+1+1+1 // A
여기서도 마지막으로 A->left 와 A->right의 총합이 어떻게 더해지는거죠? 먼저의 리턴값들은 저장안되고 다 사라져버려야 되는걸로 생각되는데…
그리고 포인터를 리커시브로 전진해가는 방법도 좀 이해가 안가고요. (물론 레프트 리커시브가 먼저 왔으므로 레프트부터 시작은 하는데 왼쪽으로 내려갔다 거슬러올라와서 다시 오른쪽을 훑으면서 다시 A의 오른쪽으로 넘어가는 과정들이 확실히 감이 잡히는건 아니네요. 그 과정에서 리턴값이 계속 더해지는것은 더 헷갈리고. ) root = root->next 는 이해가 가는데, 이걸 리커시브 함수로 해서
f( root) { …. f(root->next) …} 이건 좀 헷갈려요.
root = root->next 는 포인터를 아이터레이티브가 루프안에서 완전 끝에 도달할때까지 계속 전진해나가는걸로 이해하기 어렵지 않은데, 리커시브에서는 리턴 0 을 해버리고 더이상 전진을 안해버릴것처럼(리커시브에서는 어떤 조건이 포인터의 전진을 끝까지 계속하게 만들어주죠? 함수에서 리턴값을 돌려준후에도 계속?) 생각되던지, 포인터의 전진이 끝난건지 아니면 계속 하는지 방향은 어딘지 감잡기가 힘듭니다. 내 말이 두서가 없는거 같네요. 어쨌건 내 혼동을 명확하게 하기위해 더 생각해봐야겠어요. 이런건 사실 서로 얼굴보고 말로 설명해도 상대방을 이해시키기 힘든데, 어쨌든 설명 고맙습니다.

이런 띄어쓰기가 안 먹는군요. D는 C의 left로 예를 들었습니다.

일단 call stack에 대한 이해가 필요하실 것 같습니다.

아래 동영상 참고해 보세요. 홧팅!

이 동영상은 그냥 오버올 리뷰라 내 이해엔 별 도움이 안되는군요. 사실 바이너리추리나 바이너릿서치추리의 프리어더 인오더 포스트오더 트래스버스에 관련한 이런 리커시브는 이해가 어렵지 않은데요. 멀티플 리커시브 콜즈, Call Stack 부분이 내가 계속 파고들어야갈 부분같네요. 아이터레이티브는 그런대로 이해가 어렵지않은데 리커시브만 들어가면 내 머리가 약해져요. 특히 리커시브함수안에 여러개의 리커시브 리턴 케이스가 존재할경우.

일단 원글의 데이타스트럭춰와 관련한 리커시브에서 내가 헷갈리는 이유는 리커시브 리턴밸류나 변수들의 스코프에 대해서도 헷갈리고 있는듯하네요. (리턴밸류가 저장되어있다가 누적되는 부분. 어떻게 하위리커시브 함수 리턴밸류가 상위의 저장된값에 다시 합해져 저장되는지) 리커시브함수들에 대해서 한번 다시 먼저 살펴봐야 겠어요. 아마 내가 혼동한 부분이 리턴이 1(1번째 리턴값 1)+0 (2번째 리턴값 0)+0 (3번째리턴값 0)+0+1+0+..+1 이런식으로 리커시브가 전진할수록 누적(? 이것도 오해인듯)이 되었는데 리턴이 0일때 이전의 리턴값이 다 와이프아웃 되어버려야 된다고 생각해서였던거 같기도 하고요.

그런데 두변수 left_height와 right_height 가 함수안에서 로컬 밸류로 정의되었기 때문에, 계속 누적되는 부분이 아직도 이해가 안가네요. 각각의 리커시브가 콜링될때마다 이 값들이 다시 셋업되어 버려서 누적이 안될거 같은데…(아마 이게 내 혼동의 근원인듯하네요)

https://www.bogotobogo.com/cplusplus/stackunwinding.php
보고또보고?
이거 한국분인거 같군요? 뭐하시는분인지….여기보면 상당히 수준노푼 블로그 글들이 올라와 있군요.

오해가 풀렸네요.
내가 리커시브에 대해 오해를 한 혼동의 이유:

1. 결국 함수안에서 리턴을 두번의 케이스로 나누어하고, 두번의 리커시브 함수를 함수안에서 콜링을하니, 리커시브를 내가 제대로 이해를 못한게 원인이네요, 즉, 리커시브함수를 시퀀셜로 오픈하고 클로징하는걸로 착각해서 리턴값을 생각하려고 했네요. { 함수1 오프닝 앤 클로징} {함수2 오프닝 앤 클로징, 리턴값 함수1에 전달} {함수3 오프닝 앤 클로징, 리턴값 함수2에 전달 } 이런식으로 착각을요. 사실은 시퀀셜이 아니라
{ 리커시브 함수1 오프닝 { 리커시브 함수 2 오프닝 { 리커시브 함수 3 오프닝 and then 함수 3 클로징 } 함수2 클로징 } 함수 1 클로징 } 이런 순서였는데 말이죠.

2. 결국 1번의 착각으로 return {맥스(레프트_하이트, 라이트_하이트) + 1}; 에서 lheight 또는 rheight 가 한단계 깊은 리커시브함수의 리턴값으로부터 전달된다는 사실을 깜빡 해버린 거였네요. 하여간 멍청해서 내 두뇌 프로세스 수준이 낮으니깐 리커시브가 쪼끔만 복잡해지면 그냥 곧잘 내편할대로 착각해버리네요.

나같이 리커시브함수 이용할때 착각하는 사람 또 있을려나?

그게 recursion 실행 순서 잖아요. stack 에 대해 아시는지? LIFO 구조이고 Last in First Out 이니까 처음 root로 실행된 함수가 제일 나중의 리턴 값이 됩니다.

에를들어
1 – 2 – 3- 4 가 stack에 있다면
pop() 을 하면 4-3-2-1로 하게 됩니다.

Queue 는 달라요. 이건 들어간 순서대로 나와요. 위에 문제를 Queue로 풀수 있어요 BFS 방식으로

Queue방식은 리커시브 방식이 아니라 그냥 함수안에서 큐를 불러다 아이터레이터로 루프를 돌리죠. 이건 BFS 방식이 아니라 DFS 방식인데 착각하신듯하군요. 아 ,내가 착각했네요 ㅋㅋ BFS 가 맞네요.

그래서 크게 말하면 두가지 방식 1. 리커시브 방식과 2. 아이터레이티브 방식이 있죠. 보통 리커시브 방식이 프로그램자체는 간단한데 나같은 사람처럼 쉽게 혼동하는 사람이 있을거 같기도 해요.

리커시브 방식의 리턴값 방식은 말씀하신대로 스택 방식이네요. 원글에서처럼 리커시브 함수를 구현할때 스택 데이타 스트럭춰를 익스플리시트하게 이용한건 아니기 때문에 그런 관점에서 생각해보진 않았는데.

그나 저나
그래프 데이타 스트럭춰가 가장 흥미롭군요. 사실 그래프 이론이 상당히 흥미로운 수학 분야중 하나인데… 그래프 데이타 스트럭춰는 응용분야가 무궁무진하게 많을듯. 순수연구분야에서도 많이 쓸수 있을듯하고.

그리고 보니,
예를 들어,
인오더 트래스버설일 경우를, 1. 대부분의 경우 리커시브로 접근하면 아주 쉬운데, 2. 리커시브 방식을 쓰지 못하게 하고 BFS 로 접근하게(또는 하나의 아이터레이터 루프로만) 구현하고 싶다면 리커시브보다 상당히 복잡해질거 같은 생각이 드네요.

“2. 리커시브 방식을 쓰지 못하게 하고 BFS 로 접근하게(또는 하나의 아이터레이터 루프로만) 구현하고 싶다면 리커시브보다 상당히 복잡해질거 같은 생각이 드네요”

음 BFS로 해도 별로 어렵지 않습니다. parent에서 child로 넘어갈때 자신이 가지고 있는 height + 1을 넘겨주면 되지요. 그럼 Leaf 노드 까지 진행시 height가 증가하게 되고, 그 중에서 가장 큰 값이 Tree height가 되는 것이죠.

from collections import deque # double ended queue
def tree_height(root) {
    q = deque([(root, 1)]) # (node, height) as tuple
    treeHeight = 0
    while len(q) > 0:
        node, height = q.pop(0) # pop the first item 
        treeHeight = max(treeHeight , height) # update the treeHeight 
        if node.left:
            q.append((node.left, height+1))
        if node.right:
            q.append((node.right, height+1))

   return treeHeight 
}

deque 대신에 그냥 일반 stack으로 풀어도 결국 값은 동일합니다.
진행 순서만 다를뿐 결국 Leaf 노드까지 모두 가게 되는건 같으니까요.

def tree_height(root) {
    stack = ([(root, 1)]) # (node, height) as tuple
    treeHeight = 0
    while len(stack) > 0:
        node, height = stack.pop() # pop the last item
        treeHeight = max(treeHeight , height) # update the treeHeight 
        if node.left:
            stack.append((node.left, height+1))
        if node.right:
            stack.append((node.right, height+1))

   return treeHeight 
}

제가 제기한 문제를 오해하신 듯해요. 제가 제기한 문제는 스택이나 큐 아이터레이터를 이용해서 레벨 오더 트래버스를 시켜보라는 의미가 아니라,
어떤 바이너리 추리가 주어질때, “인오더 트레버스의 아웃풋으로 나오는 것과 같은 결과”를 나오도록, 리커시브를 전혀 이용하지 말고 한번 구현해봐라. 이런 의미였어요. 문제가 좀 다르죠? 아마 이경우는 구글해도 솔루션 찾기가 힘들걸요?

(사실 레벨 오더 트레버스의 경우는 리커시브와 아이터레이트방법 모두가 구글하면 솔루션이 다 쉽게 나오죠. 저 솔루션도 혹시 파이썬 솔루션 구글에서 카피한건가요?),

“인오더 트레버스의 아웃풋으로 나오는 것과 같은 결과”로 하려면 stack을 쓰면 됩니다.
그리고 어디서 카피 한거 아니고 그냥 쓴거에요ㅋ 둘려보지 않았지만 아마? 될겁니다. 저는 현직 개발자이고 이런 종류의 문제들은 많이 풀어봐서 구글링 없이 쉽게 할수 있어요. 이직시에 인터뷰 문제로 알고리즘 문제들이 많이 나오니까요.

in-order traversal은 recursion으로 하는게 젤 쉽지만 stack으로 푸는 것도 어렵지 않아요. 구글에 iterative in-order traversal라고 검색해 보시면 다양한 코드가 많이 나옵니다. 예를 들면 https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/ 같은 것이 있겠네요.
제가 좋아하는 방식으로 코드를 짠다면

def inorder(root):
  stack = []
  while root or len(stack) > 0:
    while root:
      stack.append(root)
      root = root.left

    root= stack.pop() # current root is Null node, so pop the last element
    # do something using the current node
    print(root.value)
    root = root.right
}

아, 구글안해봤느데….이문제도 구글 하면 솔루션이 나오는 문제였나보군요. 하긴 워낙 많은 종류의 문제들이 이미 온라인상에 있기 때문에 새로운 문제 생각해내기도 힘들듯.

“저는 현직 개발자이고 이런 종류의 문제들은 많이 풀어봐서 구글링 없이 쉽게 할수 있어요. 이직시에 인터뷰 문제로 알고리즘 문제들이 많이 나오니까요. ” => 아니 도대체 이직을 얼마나 자주 하셨길래 이런 종류의 알고리즘 문제를 항상 갈고 닦고 아무때나 풀수 있게 준비가 항상 되어있는거에요? 직접 일할때는 거의 쓸일이 없는 문제들일텐데? 이런 문제 푸는게 매일매일 생활화 되신건가요? 대단하시네요 ㅋㅋ 그럼 지금 당장이라도 또 이직 할수도 있으니까, 오늘도 인터뷰 공부하는셈 치고 내글에 댓글달면 되는거군요? 나는 1주일만 공부안하면 그 전 공부한 내용들 다 까먹어 버릴거 같은데.. ㅋㅋ 대단들 하시네요. 무슨 고시공부 시험이 한번 패스하고 마는것이 아니라 항상 준비되어있어야 하듯이 ㅋ 평생 고시공부하는거처럼 ㅋㅋ 그럼 여기 댓글 다는 코딩하는 분들은 코딩 공부가 아예 생활화 되셨을수도 있겠군요…그러고보니, 한곳에 오래있다 나이들어 이직해야 하는 분들은 이런거 준비해두기가 쉽진 않겠군요.

어쨌든 답변 주셔서 고맙습니다. 그런데 mss 님은 씨뿔뿔이나 자바는 별로 안쓰시고 파이쏜을 주로 쓰시나요? 에이아이나 머신러닝은 파이쏜이 용이하지만, 알고리듬 문제들은 파이쏜보다는 자바나 씨뿔뿔이 더 훨씬 접근이 용이할듯한데?…

“이런 문제 푸는게 매일매일 생활화 되신건가요? 대단하시네요 ㅋㅋ 그럼 지금 당장이라도 또 이직 할수도 있으니까, 오늘도 인터뷰 공부하는셈 치고 내글에 댓글달면 되는거군요? 나는 1주일만 공부안하면 그 전 공부한 내용들 다 까먹어 버릴거 같은데.. ㅋㅋ 대단들 하시네요. 무슨 고시공부 시험이 한번 패스하고 마는것이 아니라 항상 준비되어있어야 하듯이 ㅋ 평생 고시공부하는거처럼 ㅋㅋ 그럼 여기 댓글 다는 코딩하는 분들은 코딩 공부가 아예 생활화 되셨을수도 있겠군요…그러고보니, 한곳에 오래있다 나이들어 이직해야 하는 분들은 이런거 준비해두기가 쉽진 않겠군요.”

=> 매일매일 문제 풀이를 생활화 하지는 않아요 ㅎㅎ 저도 하기도 싫고 머리가 나쁜지 또 반년쯤 지나면 까먹습니다 ㅠㅠ 또 업무에서 사용하는 지식과 살짝? 동떨어져 있기 때문에 인터뷰 시즌이 오면 눈물을 머금고 다시 공부를 시작하죠. 저는 혹시 모를 레이오프와 이직 가능성을 염두에 두고 조금씩 짬을내서 문제풀이를 퇴근후에 하고 있어요. 농담으로 “one leetcode a day keeps unemployment away” 라는 말이 있을 정도로.. ㅎㅎ 운동하듯이 꾸준히 하는 분들 많을 겁니다.

“mss 님은 씨뿔뿔이나 자바는 별로 안쓰시고 파이쏜을 주로 쓰시나요 에이아이나 머신러닝은 파이쏜이 용이하지만, 알고리듬 문제들은 파이쏜보다는 자바나 씨뿔뿔이 더 훨씬 접근이 용이할듯한데?”

=> 파이썬이 오히려 “빠른 문제풀이”에 최적화 되어 있어요. 코드를 보시면 아시겠지만 typing도 없고 코드가 pseudo 코드처럼 간단하기 때문이에요. 코비드 전에 인터뷰불때 화이트보드에 코드를 적어서 설명을 해야 하는데 파이썬으로 하면 설명이 간결해 지지요.
그래서 제 주력언어는 아니지만 문제풀이는 파이썬으로 합니다. 물론 Competitive programming 대회에서 “빠른 실행결과” 를 위해서는 말씀하신 언어인 low level 언어인 c++이 제일 선호되는것 같아요

한번 공부해두면 6개월을 간다니…..대단한 메모리의 소유자시네요 ㅋㅋㅋ 아니 근데 이런 인터뷰 방식이 포말라이즈된게 약 5-6년 된건가요? 너무 이직하기 힘들겠다. 이건 뭐 이직하려면 거의 박사 퀄리 파이 준비하는 것처럼 준비해야 할거 같은데…

파이썬이 알고리듬 문제 풀때 더 간단하다는 건 의외군요. 흠…나도 파이썬으로 갈아타볼걸 고려해봐야 하나? 파이썬으로 그쪽 관련된 라이브러리는 써본적이 없어서 아예 데이타스트럭춰쪽은 파이쏜으로 아예 시도조차 안해봤는데…근데 난 어차피 결국 파이썬 써야 할거 같은데…

Tree는 graph의 special한 케이스이고 물어보신 문제는 가장 기본중에 기본이고 그 외에도 다양한 분야에 graph 이론과 관련된 알고리즘과 그 응용은 무궁무진 합니다.
DFS, BFS, Disjoint-sets, Minimum Spanning Tree, Shortest Path, Topolocal Sort…..
어떤 것들이 있나 간략하게 보시려면 아래 유트브 채널을 추천 합니다.
https://www.youtube.com/@WilliamFiset-videos

그나저나
데이타 스트럭춰나 알고리듬에 사람들이 관심이 많나요? 컴싸 전공자들이 많은 것도 아닐텐데…..클릭수가 생각보다 상당히 많네요? 뒷마당에 있는 나무 높이을 어떻게 잴까 하는 문제로 생각들하고 아무생각없이들 클릭들 한건가? 어제는 무조건 욕하는 댓글달러 들어온 철딱써니 개뼉다귀도 하나 있더구먼…

근데 이 간단한 함수를 이렇게까지 이해못하는거면 그냥 이쪽분야에 약하신거 같음

맞아요.
예전에 박사논문 쓸때, 코딩하다가 머리 뒷꼴에 두통생겨 아주 코딩쪽 소질 없다는거 이미 알았어요. 루프돌리고 이리저리 꼬아서 함수로 보내고….따라가는거 정말 머리아픔. 심지어, 처음 시뿔뿔 배울때 컨스트럭터 매개변수로 들어가는 퍼블릭 변수가 프라이빗 변수가 있는데도 왜 또 필요한지도 이해 못했음. 첫번째 중간고사 데이타스트럭춰 클래스배울때 꼴찌에서 두번째 했음..(아..내밑에 좀 더 있긴 있었는데 걔네들 다 포기하고 드랍해버렸던듯) 지금보니 그때 뭘배웠는지 생각나는게 하나도 없네…역사적인 기록ㅋㅋㅋ. 중국애가 꼴찌하고. 두번째 시험에서 좀 만회하긴 했지만. 그래뵈도 에스티메이션 클래스에서는 앞에서 일등했었는데…

1234님도 그렇게 쉬운거 같으면 내가 위에서 제기한 문제 한번 풀어보시구요. 솔직히 대부분 솔루션들이 구글만 하면 솔루션들이 나오는 판박이 유형 문제들이라…근데 아래문제는 내가 내는거니 구글해도 아마 없을걸요.

아래 문제 다시 카피/페이스트해볼테니 한번 꼭 풀어봐요. 얼마나 똑똑한지 좀 보게.

스택이나 큐 아이터레이터를 이용해서 레벨 오더 트래버스를 시켜보라는 의미가 아니라,
어떤 바이너리 추리가 주어질때, “인오더 트레버스의 아웃풋으로 나오는 것과 같은 결과”를 나오도록, 리커시브를 전혀 이용하지 말고 한번 구현해봐라. 이런 의미였어요. 문제가 좀 다르죠? 아마 이경우는 구글해도 솔루션 찾기가 힘들걸요?