[알고리즘] 반복법, 재귀법 개념 이해

프로그래밍을 배우면 거의 초반부에 반복법을 배우게 됩니다. 루프를 반복하다가 특정 종료 조건을 만나면 멈추는 반복법은 개념을 이해하기가 그리 어렵지 않습니다. 그 후 프로그래밍을 계속 배우다 보면 재귀법을 만나게 됩니다. 보통 반복법과 재귀법이 같이 나오면서 둘을 비교하면서 설명하기도 하고 같은 프로그램을 반복법과 재귀법으로 2개를 만들어보라고도 합니다. 그런데 저의 경우에는 반복법의 코드는 원형 회귀를 하는 이미지가 떠오르며 쉽게 이해가 되었는 데 재귀법의 코드를 봤을 때에는 직감적으로 이미지가 떠오르지 않았습니다. 그래서 한동안은 제대로 이해를 하지 못하고 그냥 외워서 사용했습니다. 그러나 재귀법 예제들을 계속 보다보니 특정한 이미지가 떠오르게 되었습니다. 그래서 재귀법을 이해하는데 어려움을 느끼는 분들에게 도움이 되도록 제게 떠오른 이미지를 정리해봤습니다.

먼저 흰 공이 있습니다. 이 공을 반복법 혹은 재귀법 코드에 통과시켜 황금공(답)을 얻어야 합니다.

 

반복법의 경우: 일반 흰 공을 떨어뜨리면 매 반복마다 for loop 등의 내부 코드가 공을 황금칠을 해주며 종료 조건을 만나면 황금공 칠하기가 완료됩니다.

 

재귀법의 경우: 탱탱볼 흰 공을 떨어뜨리면 일단 재귀법 함수의 점화식 등에서 황금칠을 하지 않고 Base Case에 다다를 때까지 그대로 통과합니다. Base Case를 만나면 흰 공은 첫번째 황금칠을 하게 되고 다시 위로 튀어오릅니다. 튀어올라 다시 점화식을 거슬러 올라가며 재귀법 함수의 코드를 거쳐가 황금칠을 하게 됩니다. 그리고 공을 떨어뜨렸던 지점까지 다시 올라오게 되면 황금공 칠하기가 완료됩니다.

 

---

피보나치 수열의 경우

반복법

for (int i = 2; i < n; i++) {
   f = fpp + fp
   fpp = fp
   fp = f
}

f = fpp + fp
fpp = fp
fp = f

의 코드 블럭을 거쳐갈 때마다 1번씩 황금칠을 하게 되며

i < n

의 종료 조건을 만나면 황금공 칠하기가 완료됩니다.

 

---

재귀법

if (n <= 1)
   return 1
return fib(n - 1) + fib(n - 2)

n = 5 일 경우

return fib(4) + fib(3)

return fib(3) + fib(2)

return fib(2) + fib(1)

...

여기까지는 황금칠을 하지 않고 그대로 통과합니다.

return 1

return fib(2) + fib(1)

return fib(3) + fib(2)

return fib(4) + fib(3)

Base Case에서 튀어올라 재귀법의 점화식을 다시 거슬러 올라가며 황금칠을 하게 됩니다.

처음 시작했을 때로 되돌아 오면 황금공 칠하기가 완료됩니다.

 

 

 

이상이 제게 떠오른 재귀법의 작동 이미지였습니다. 재귀법을 이해하는데 조금이나마 도움이 됬으면 좋겠습니다.