C++ 기초 : 재귀 함수 (1)

---

함수는 스택 방식, 즉 선입후출(후입선출) 방식으로 작동한다고 했습니다.

이러한 함수는 스택 메모리 영역에서 작동하죠.

 

이 과정을 디버깅을 통해 눈으로 확인할 수 있습니다.

 

 

Factorial 함수 코드를 디버깅해서 확인해 보죠.

 

19번째 줄에 중단점을 찍고 디버깅을 시작했습니다.

 

일단 main 함수가 호출되면서 사용할 변수들(iValue, iValue1, iValue2)을 할당했습니다.

'로컬'을 보면 아직 초기화까지 진행되지 않아 각 변수들에는 쓰레기값이 들어가 있네요.

 

오른쪽 하단에 "호출 스택"이라고 있습니다.

현재 어떤 함수가 호출되어 쌓여 있는지 보여주는 곳입니다.

현재는 main 함수만 있습니다.

 

 

이제 F11을 눌러서 한 단계 더 진행하겠습니다.

 

화살표가 Factorial 함수로 이동했습니다.

 

왼쪽 하단에 로컬을 보면 현재 들어간 함수,

즉 Factorial 함수에서 사용되는 변수들이 보입니다.

아직 함수가 호출되기만 해서 쓰레기값이 들어가 있습니다.

 

호출 스택에 Factorial 함수가 쌓인 게 보입니다.

 

main 함수에서 변수 iValue에 넣을 값으로 Factorial 함수를 호출하였으니 

main 함수 위에 Factorial 함수가 쌓인 것이죠.

 

 

참고로 다른 함수가 진행 중일 때, 다른 함수의 로컬 상황을 보고 싶다면

보고 싶은 함수를 호출 스택에서 더블클릭하면 됩니다.

 

Factorial 함수에서 디버깅을 진행하는 도중,

호출 스택에서 main 함수를 더블클릭하니

로컬에 main 함수의 상황이 나타납니다.

 

 

다시 돌아와서

 

13번째 줄에 중단점을 찍어서 for 문을 한 번에 진행합니다.

 

로컬을 확인해 보니

Factorial 함수의 지역변수 _iNum에는 

main 함수에서 받은 값인 4라는 값이 들어가 있습니다.

 

Factorial 함수의 다른 지역변수 iReturnValue에는

for 문을 수행하고 얻은 값인 24가 들어가 있습니다.

 

 

이제 디버깅을 더 진행하면 

 

Factorial 함수는 소멸되며

변수 iReturnValue에 들어있는 값을 main 함수에 반환하게 됩니다.

 

 

 

이후 F11을 눌러 한 단계 더 디버깅을 진행하니,

 

main 함수의 지역변수 iValue에  반환한 값이 대입된 것을 확인할 수 있습니다.

 

 

 

여기서 생각해 볼 점이 있습니다.

Factorial 함수에서 main 함수로 이동하여 값을 반환하려면

Factorial 함수가 먼저 소멸되어야 main 함수로 이동할테고

변수 iValue에 값을 넣을 수 있을 겁니다.

 

근데 그렇게 되면 24라는 값은

Factorial 함수가 소멸하며 같이 사라지는 문제가 발생합니다.

 

하지만 디버깅 내용을 보면 잘 작동하는 것을 볼 수 있는데요.

왜 그럴까요?

 

컴퓨터에서는 이러한 문제 때문에

함수에서 반환하는 값을 레지스터라는 기억 장소에 넣습니다.

 

덕분에 값을 반환한 Factorial 함수가 소멸되더라도

main 함수는 레지스터에 저장된 24라는 값을 꺼내

변수 iValue에 24를 대입할 수 있는 것이죠.

 

 

 

 

 

 

---

 

 

 

 

 

 

재귀 함수는 함수 내에서 자기 자신을 다시 호출하는 것입니다.

 

 

아래 코드에서 14번째 줄을 보면

 

Factorial 함수 내에서 다시 Factorial 함수를 호출하였죠.

 

이러한 방식이 재귀 함수입니다.

 

만약 저 상태 그대로 실행하면 어떻게 될까요?

 

 

먼저 main 함수가 실행될 것입니다.

 

22번째 줄에서 Factorial 함수가 호출되었으므로

5번째 줄로 가서 Factorial 함수를 실행하겠네요.

쭉 실행하다가 14번째 줄에서 다시 Factorial 함수를 만납니다.

 

그러면 다시 5번째 줄로 가서 Factorial 함수를 실행하겠네요.

쭉 실행하다가 14번째 줄에서 다시 Factorial 함수를 만납니다.

 

또다시 5번째 줄로 가서 Factorial 함수를 실행하면서 

위 과정을 계속 반복하게 될 겁니다.

 

 

스택 메모리 영역은 아래와 같이 되겠죠.

 

Factorial 함수가 소멸되는 시점이 없이

Factorial 함수를 계속 호출하고 있으므로 

스택 메모리 영역이 계속 채워지기만 할 겁니다.

 

그러다가 한계에 다다르면 오류가 발생합니다.

 

이때 발생하는 오류가 바로 "Stack overflow" 입니다.

 

 

실행해 보면 아래와 같이 오류가 발생하는 것을 확인할 수 있습니다.

 

 

정말 많은 Factorial 함수가 호출 스택에 쌓였습니다.

 

 

가장 밑에는 main 함수가 보이네요.

 

 

 

 

 

---

 

 

 

 

 

재귀 함수는 잘못 사용하면 Stack overflow가 발생하므로 조심히 사용해야 합니다.

 

Stack overflow는 수정하면 해결되지만,

재귀 함수의 또 다른 문제는 바로 성능입니다.

 

같은 함수라도 여러 번 호출할 때마다 별도의 스택으로 구분합니다.

그때마다 지역변수, 매개변수(함수명 괄호 안에 있는 변수),

반환값을 저장해야 하니 메모리를 많이 사용합니다.

게다가 함수를 호출하고 소멸하면서 다시 돌아갈 때 비용이 또 들어가죠.

 

심지어 재귀 함수는 반복문으로 대체하여 사용할 수 있습니다.

반복문은 선언한 변수만 사용하므로 메모리도 비교적 적게 사용합니다.

 

 

단점이 많아 보이는 재귀 함수는 왜 사용하는 걸까요?

 

반복문이 재귀 함수를 대체할 수 있듯이, 재귀 함수도 반복문을 대체할 수 있습니다.

가독성이 좋지 않은 반복문 대신 사용하여 가독성을 높일 수 있습니다.

 

또한 계층구조를 간략하고 편하게 구현할 수 있고

다른 사람이 봤을 때도 무엇을 하는 코드인지 파악하기가 쉽습니다.

 

하나의 함수에 여러 개 변수를 선언하여 사용해야 하는 경우,

재귀 함수를 통해 변수의 개수를 줄일 수 있습니다.

 

아래 그림을 보면 

 

코드를 통해 직접 선언한 변수는 _iNum과 iReturnValue,

두 개밖에 없지만 재귀 함수를 통해 여러 스택이 쌓이면서

각각 스택에 다양한 변수의 상태가 담길 수 있습니다.

 

가장 처음에 쌓인 Factorial 함수의 변수 _iNum의 값과 

이후 쌓인 Factorial 함수의 변수 _iNum의 값이 다릅니다.

이를 마치 다른 변수처럼 사용할 수 있게 되는 것이죠.

 

 

 

 

강의 출처 : https://www.youtube.com/watch?v=PFc4g8mxOiI&list=PL4SIC1d_ab-aOxWPucn31NHkQvNPHK1D1&pp=iAQB

 

---