프로그래밍 입문자들에게 강의를 할 때, 항상 장벽처럼 느껴지는 주제들이 있습니다.  포인터, OOP, 비동기 처리 등이 그렇습니다.  그리고, 오늘 이야기하려고 하는 재귀 호출 또한 큰 장벽이 됩니다.


"어떻게 하면 재귀 호출을 쉽게 설명 할 수 있을까?"


처음에는 어떻게 하면 쉽게 설명 할 수 있을 까 고민을 많이 해봤습니다.  하지만, 번번히 실패하고 말았습니다.  그래서, 질문을 바꿔 보았습니다.


"재귀 호출을 이해하는 것이 왜 어려울 까?"


그리고, 찾아낸 것이 바로, 입문자분들께서 함수 호출 과정 자체를 제대로 이해하지 못하고 있다는 것을 깨달았습니다.  따라서 오늘은 먼저, 재귀 호출을 설명하기 전에 우선 함수 호출 과정을 살펴보도록 하겠습니다.  (소스 내에 문법에 어긋난 곳이 있습니다)




함수의 호출 과정


[그림 1]에서 보면 CPU에 의해서 실행되고 있는 코드가 빨간색 화살표로 표시되고 있습니다.  age 변수에 숫자 1을 대입하고 있습니다.  


[그림 1]


[그림 2]는 코드가 좀 더 진행되어서 2번 째 라인에 있는 incAge() 함수를 호출합니다.


[그림 2]


[그림 3]에서는 함수를 실행하는 중간입니다.  아직 함수가 있는 B 코드 영역으로 이동하지는 못하였습니다.  다만, 오른쪽에 있는 Stack에 보시면, "A.3의 주소"가 저장되었습니다.  이는 [그림 2]에서 incAge() 함수를 호출하기 전에 있었던 라인의 바로 다음 라인이 됩니다.


[그림 3]


[그림 4]에서는 이제 코드 진행이 B 코드 영역의 3 번 라인을 실행하고 있습니다.  age 변수에 있는 값이 숫자 1 만큼 증가하여 대입됩니다.  결과적으로 2가 될 것 입니다.


[그림 4]


[그림 5]에서는 incAge() 함수의 실행이 끝나고 종료되는 순간입니다.   Stack에 있는 가장 최근 데이터를 가져옵니다.  "A.3의  주소"가 저장되어 있습니다.  따라서, 코드 진행은 A 코드 영역의 3번 라인으로 이동합니다.



[그림 5]


[그림 6] 에서는 다시 함수에서 되돌아 와서 원래 코드의 진행이 계속 됩니다. 


[그림 6]


함수에서 return의 의미는 이처럼 "스택에 저장 된 최근 주소, 즉, 나를 실행시킨 라인 바로 다음 라인의 주소로 돌아간다" 라는 의미입니다.  (우리가 작성하는 코드와 기계가 실제 인식하는 코드의 라인은 서로 다릅니다)


왜 이렇게 하고 있을까요?  외부 함수는 현재 진행 코드와는 일반적으로 동 떨어진 곳에 있기 마련입니다.  그리고, 해당 함수를 호출하는 곳이 한 곳이 아니기 때문에, 함수는 자신이 실행되고 난 뒤에 되돌아 갈 곳이 항상 바뀔 수 밖에 없습니다.  결국 되돌아 갈 곳이 어딘지를 저장해둬야 합니다.


그렇다면, 왜 Queue가 아니고 Stack을 사용하고 있을까요?  A() 함수가 B() 함수를 호출하고, 이제 B() 함수가 C() 함수를 실행 시켰다고 가정하겠습니다.

  • A() --> B() 호출 할 때 되돌아 갈 A() 주소를 저장합니다.
  • B() --> C() 호출 할 때도 되돌아 갈 B() 주소를 저장합니다.
  • C() 실행이 종료되면 B()로 돌아가야 하나요?  A() 로 돌아가야 하나요?
당연히 B()로 돌아가야 합니다.  B() 주소는 A()보다 나중에(최근에) 저장되었습니다.  최근에 저장 된 것이 먼저 출력되는 데이터 구조가 필요합니다.  즉, Stack을 사용 하게 되는 것 입니다.

잠시!!!!
일단 이 부분이 확실하게 이해가지 않는다면, 함수 호출 과정 자체를 심도 깊게 공부하셔야 합니다.  위의 설명은 파라메터 관리 등에 대한 세밀한 언급을 피하고 최대한 간략하게 설명한 것입니다.  하지만, 지금까지의 이해가 부족하다면 재귀 호출 뿐 아니라, 다른 공부를 진행하는데에도 언젠가는 방해를 받게 될 것 입니다.



재귀란?

[그림 7] 부문의 패턴의 반복으로 전체의 패턴인 피라미트 구조체 (출처: http://commons.wikimedia.org)


"재귀란 반복 현상입니다.  
그리고, 
그 반복 속에서 일정한 형태를 유지하고 있는 경우를 의미합니다."

재귀는 특정 패턴이 반복되면서 거대한 구조를 만들었을 때, 그 구조물 전체가 다시 특정 패턴이 되는 것을 의미합니다.



1차원적 재귀

좀더 이해를 돕기 위해서, 1부터 시작해서 1씩 증가하는 순차 순열의 합을 통해서 1차원적 재귀 문제를 다뤄보도록 하겠습니다.

Sum = 1 + 2 + 3 ..... n

자, 이것을 순서대로 합을 나열해 보겠습니다.  Sum(n)은 n까지의 합을 의미합니다.

Sum(1) = 1
Sum(2) = Sum(1) + 2
Sum(3) = Sum(2) + 3
.....

"Sum(n) = Sum(n-1) + n" 형태가 n 값만 변경 된 상태에서 계속 반복되는 것을 알 수가 있습니다.  
  • 일단 Sum(n)의 결과값이 무엇인지 모르겠습니다.
  • 하지만, 만약 Sum(n-1)까지 구한 값이 있다면, Sum(n)은 거기에 n만 더하면 됩니다.
  • Sum(n)에게 결과값을 물어 봤더니, Sum(n)은 자기 자신인 Sum()에게 Sum(n-1) 값을 요구합니다.
  • Sum()은 항상 일관적인 행동을 하는 심지가 굳은 놈입니다.  그래서 Sum(n-1)은 Sum(n-2)에게 값을 요구합니다.
  • Sum(1)은 Sum(0)에게 물어보고 싶은 마음은 굴뚝 같지만, 문제의 시작에서 "1부터 시작해서" 라는 전제에 의해서 억울하지만, 1이라는 값을 Sum(2)에게 알려줍니다.  
  • Sum(2)는 Sum(1)이 알려준 1의 값에 2를 더해서 Sum(3)에게 알려줍니다.  그렇게 Sum(n-1)에게 까지 전달되면 Sum(n-1)은 결과에 n을 더해서 Sum(n)에게 알려주고 이제 Sum(n)은 최종 답을 알게 되는 것 입니다.
이러한 것을 점화식이라고도 부릅니다.  Sum(1)부터 화르륵 타올라서 Sum(n)까지 도달해서 끝이 나는 모양을 표현 한 것 입니다.

다음의 소스는 이것을 코드로 표현한 것 입니다.  막내가 바로 "탈출구" 또는 "탈출조건"이 됩니다.  만약 저러한 탈출구가 없다면, 계속 함수가 반복되어 자기 자신을 실행 할 것 입니다.  그러면 스택에 데이터가 점점 쌓이게 되고 언젠가는 스택의 메모리 부족(Stack Overflow)으로 에러가 나게 됩니다.  (함수 호출은 스택에 실행 된 곳 이후 라인이 항상 저장 되는 것을 상기하시기 바랍니다)

int Sum(int n)
{
	// 막내의 설음 ㅠ.ㅠ
	// 서럽지만 시킬 사람이 없다.
	// 그냥 내가 계산해 줄께, 답은 1이다 ㅠ.ㅠ
	if (1 == n) {
		return 1;
	}

	// 내가 계산하기 구찮다 아우야 니가 계산하고
	// 나는 거기에 n만 더할께
	else {
		return Sum(n-1) + n;
	}
}

코드를 완전하게 이해하기 위해서 Sum(3)의 과정을 컴퓨터의 입장에서 따라가 보도록 하겠습니다.  빨간 라인이 실제 실행되는 경로입니다.


[그림 8]


[그림 8]을 이해하려면 Sum(3), Sum(2), Sum(1)을 일종의 분신처럼 생각해야 합니다.  1부터 3까지 더하는 것을 세 명에게 나눠서 분업 시키는 결과와 같기 때문입니다.  다만, 멀티 스레드를 사용한 것은 아니기 때문에 한 번에 하나씩만 실행됩니다.  따라서, 위의 과정을 아래처럼 해석 할 수 있습니다.

  • Sum(3)이 13: 번 라인에서 분신 Sum(2)를 만들고 자신을 잠시 얼려 둔다.
  • 이제 Sum(3)은 굳어버린 상태이고, Sum(2)가 활동한다.  6: 라인에서 조건이 맞지 않기 때문에 Sum(3)과 마찬가지로, 13: 번 라인에서 새로운 분신 Sum(1)을 만들고 자신을 잠시 얼려 둔다.
  • Sum(1)은 6: 라인의 조건을 만족하기 때문에 "return 1"을 외치면서 사라진다.
  • 분신이 사라지자, 얼었던 Sum(2)가 다시 살아난다.  그 동안 무슨 일이 있었는 지는 모르지만, "return 1" 메시지가 전달 된다.
  • Sum(2)는 "return 1" 메시지에 2 를 더하여 "return 3"을 외치면서 사라진다.
  • 분신이 사라지자, 얼었던 Sum(3)이 다시 살아난다.
  • Sum(3)은 "return 3" 메시지에 3 를 더하여 "return 6"을 외치면서 사라진다.
  • Sum(3)의 메시지는 Sum(3)을 호출한 곳으로 전달된다.


그리고, 위의 과정은 "함수 호출 과정"에서 다뤘던 스택의 상태까지 함께 머리에 그릴 수 있어야지만 정확한 이해가 완성되는 것 입니다.




다차원적 재귀


다차원적 재귀에서 가장 흔하게 보이는 문제는 "미로 찾기", "폐곡선 내부에 색 채우기" 그리고 "하위 폴더 전체 검색" 등이 있습니다.  


그런데!  왜?

1차원적 재귀 문제인 팩토리얼 구하기는 쉽게(?) 이해가 가는데, 2차원만 되기 시작해도 어려워 질까요?


1차원적 재귀 문제를 이해했다면, 다차원적 재귀는 따로 이해해야 하는 것이 아닙니다.  두 문제가 본질적으로 같기 때문입니다.  




다차원적 재귀는 이해가 아닌 익숙해져야 하는 대상입니다.


김 노인과 박 노인이 장기를 둡니다.  김 노인이 날카로운 수를 두자, 박 노인이 시간을 끌며 생각에 잠깁니다.


"이 놈 봐라!  내가 여기에 두면 차로 덤비겠지, 그럼 나는 마로 방어하고 음.. 그리고.. 그리고...

그런데, 차로 안 덤비고 포로 덤비면 어떻게 하지?"


그렇게 수 없는 재귀적 조합을 통해서 경우의 수를 생각하다가,


"아, 장기 두는 넘 어디 갔나?"


김 노인이 갑자기 끼어드는 바람에 생각 해 둔 수를 모두 잊고 맙니다.


"아까 어디까지 생각 했더라?"


다시 처음부터 생각을 시작합니다.


다차원적 사고라는 것은 인간에게 있어서 자연스럽지 못한 행동입니다.  따라서, 상당한 연습을 통해서 익숙해져야 하는 것 입니다.  


마치 장기나 오목과 같은 보드 게임을 잘하는 사람들이 특별한 요령을 아는 것이 아닌 것처럼, 오랜 기간 반복 훈련을 통해서 익숙해져 가는 것 입니다.




하위 폴더 찾기에 대한 두 가지 해법


우선 다음의 코드는 재귀 호출을 이용한 방법입니다.  

// 재귀 호출을 이용한 방법

void searchFolder(String name)
{
  findFirst();
  while (찾은 것이 있다면) do {
    if (찾은것 == 폴더) SearchFolder(name + '\' + 찾은것);
    else 찾은_파일_처리();    
    findNext();
  }
}

이어지는 코드는 Stack을 이용한 방법입니다.  폴더를 검색하다가 하위 폴더가 나타나면, 스택에 쌓아 두고 원래 검색하던 것을 그대로 진행합니다.  원래 진행하던 폴더 검색이 끝나면 스택에서 가장 최근 것을 찾아서 다시 검색을 진행합니다.  큐를 사용하여도 상관없습니다.


재귀 호출을 사용한 것보다 코드가 복잡해졌지만, 성능면에서는 효율적입니다.  폴더를 검색하다 말고 다른 폴더로 이동했다가 다시 돌아오지 않고 현재 프로세스를 계속 이어 갈 수 있기 때문입니다.  요즘은 하드 디스크 입출력 및 기타 하드웨어 속도가 빠르기 때문에 크게 차이는 없습니다.  


일단 Stack 0verflow 문제에서는 쉽게 벗어 날 수 있습니다.  (Stack 클래스가 Heap 메모리를 사용하도록 구현 한다면)

// Stack을 이용한 방법

void workWithFolder(String name)
{
  findFirst();
  while (찾은 것이 있다면) do {
    if (찾은것 == 폴더) Stack.push(name + '\' + 찾은것);
    else 찾은_파일_처리();    
    findNext();
  }
}

void searchFolderUsingStack(String name)
{
  workWithFolder(name);
  while (false == Stack.isEmpty) {
    workWithFolder(Stack.pop());
  }
}




재귀적 문제가 중요한 이유


실무에서는 비교적 재귀적 문제가 자주 나타나지 않습니다.  더구나 재귀적 문제는 일반적인 해법으로도 해결이 가능합니다.  심지어 메모리 및 프로세스 효율면에서도 재귀 호출보다는 일반적인 해법이 더욱 유리합니다.  특히, 1차원적 재귀 문제들은 재귀 호출은 조금 과하다는 생각마저 듭니다.


그렇다고 재귀 호출이 무조건 나쁘다는 것은 아닙니다.  

  • 재귀 호출
    • 간결하고 직관적인 코드를 제공 (한 편의 시)
  • 일반적인 해법
    • 소설처럼 장황하지만 이해하기 쉬운 코드를 제공 (가독성은 떨어질 수 있음)
    • 메모리 및 프로세스 효율적인 코드

하지만, 재귀적 문제를 열심히 훈련해야 하는 이유는 설계와 개발 그리고 디버깅 과정 모두가 재귀적인 사고력을 요구한다는 것 입니다.


이미 장기 두는 노인분들의 예를 들었듯이, 복잡한 문제들은 다양한 경우 수를 두고 각각의 연관 관계를 살펴봐야 하는 경우가 많습니다.  디버깅의 경우에도 여러 가지 시나리오를 서로 비교하고 연구해야 하는 경우가 생깁니다.  그리고, 재귀 호출 형식이 아니더라도 재귀적인 개념이 필요한 문제 영역도 상당히 자주 만나게 됩니다.




좀 더 재귀적인 문제를 연구하고 싶은 분들은

  • Composite pattern
  • Back tracking
  • 파서와 컴파일러







저작자 표시 비영리 변경 금지
신고

Posted by 류종택


티스토리 툴바