2024. 3. 4. 14:39ㆍProgramming Language/C++
아래 링크 클릭 시 해당 본문으로 이동
호출 스택(Call Stack)
• 현재 호출되어 있는 함수들의 메모리 상황을 보여준다.
• 프로그래밍하는 데 있어서 어떤 문제점을 추적할 때 쓰인다.
디버깅 중, 호출 스택이 보이지 않을 때 : [디버그] - [창] - [호출 스택]
로컬 창과 호출 스택 장점
• 로컬 창 : 현재 중단점이 걸려있는 지역(로컬)에 존재하고 있는 변수들을 보여준다.
• 로컬과 호출 스택을 잘 활용하면 문제점을 빨리 찾을 수 있다.
훨씬 복잡한 코드도 눈으로 확인했을 때보다 문제점을 빠르게 파악할 수 있다.
• 현재 코드가 어떤 식으로 동작하고 있는지 빠르게 파악할 수 있다.
• 활용 방법 : 문제가 생긴 지점에 중단점을 걸어놓고 메모리 값 등을 로컬 창과 호출 스택으로 다른 지역(함수)을 확인하면서 어떤 상황인지 파악하면 된다.
팩토리얼(Factorial)
• 1부터 n까지의 자연수를 곱한다.
• n! = 1 x … x (n-2) x (n-1) x n
ex) 5! = 5 x 4 x 3 x 2 x 1 → 5! 는 4번 곱한다. ➜ n! 은 (n-1)번 곱한다.
재귀함수(Recursive Function)
• 함수 안에서 자기 자신을 호출하는 함수
재귀함수를 반복문으로 대체 가능하긴 하지만 스택이나 큐를 활용해야 돼서 까다롭고 복잡해진다.
그래서 재귀함수는 프로그래밍이 어느 정도 익숙해지면 사용하고 초반에는 잘 사용하지 않는다.
• 재귀함수를 사용할 때 탈출 조건이 있어야 한다.
탈출 조건이 없으면 스택 오버 플로우라는 오류가 발생한다.
• 스택 오버 플로우(stack overflow) : 재귀함수를 잘못 사용하면 나타나는 대표적인 오류로, 스택이 계속 쌓이다가 스택 메모리 영역의 한계치를 넘어갈 때 발생한다.
▷ 예시 (스택 오버 플로우)
int Factorial(int _count)
{
int value = 1;
for (int b = 0; b < _count - 1; ++b)
{
value *= (b + 2);
}
Factorial(10); // 자기 자신 호출
return value;
}
int main()
{
int value = Factorial(3);
value = Factorial(15);
return 0;
}`Factorial(10)`을 만날 때마다 `Factorial()`가 진행되고 스택도 계속 쌓인다.
결국엔 스택 메모리 영역의 한계치를 넘어가서 스택 오버 플로우가 발생한다.
오류가 발생하기 전에 호출 스택에서 아무리 마우스 휠을 내려도 잘 안 내려가진다.
∴ 스택 오버 플로우가 뜨지 않게 하려면 반드시 탈출 조건이 있어야 된다.
재귀함수 장점
• 가독성이 좋다.
• 구현하기가 직관적이라서 용이하다.
• 깔끔하고 보는 사람도 코드에 대해 쉽게 파악할 수 있다.
재귀함수 단점
실수할 여지가 있다. (ex. 스택 오버 플로우) 하지만 오류는 고치면 돼서 큰 문제는 아니다.
• 치명적인 문제 : 성능이 많이 떨어진다.
함수를 호출할 때마다 스택이 쌓이고, 각각의 스택에 남아있는 데이터들이 역으로 되돌아나가면서 재활용된다.
함수를 여러 번 호출할 때마다 각각의 스택에 남아있는 값들을 지역변수들처럼 활용(호출 및 해체)하는 개념이라서 함수 호출 비용과 함수 해체 비용이 든다.
당연히 이 비용들이 많이 들수록 성능은 떨어진다.
1. 팩토리얼 ➜ 반복문
ex) 7!.
int main()
{
// 1부터 7까지 곱한다.
int a = 7;
int value = 1;
// 7 - 1 = 6번 반복
for (int b = 0; b < a - 1; ++b)
{
// 1 다음에 2가 곱해져야 되기 때문에 b에 2씩 더한다.
value *= (b + 2); // 2부터 7까지 곱한다.
}
return 0;
}Q. `b`에 1이 아니라 2를 더한 이유는?
A. `value`를 1로 정하면 1부터 곱해지는데 1은 어떤 자연수와 곱해도 값에 변화를 주지 않기 때문에 2를 더했다.
① b = 0
`int b = 0; b < a - 1; ++b`
➜ 0 < 7 - 1 → 0 < 6 → true
`value *= (b + 2)`
➜ 1 x (0+2) = 1 x 2 = 2
② b = 1
`int b = 0; b < a - 1; ++b`
➜ 1 < 7 - 1 → 1 < 6 → true
`value *= (b + 2)`
➜ 1 x (1+2) = 1 x 3 = 3
⋯
③ b = 5
`int b = 0; b < a - 1; ++b`
➜ 5 < 7 - 1 → 5 < 6 → true
`value *= (b + 2)`
➜ 1 x (5+2) = 1 x 7 = 7
④ b = 6
`int b = 0; b < a - 1; ++b`
6 < 7 - 1 → 6 < 6 → false
`value *= (b + 2)`
1 x (6+2) = 1 x 8 = 8
호출 스택에서 값 확인하기
① `value` 값을 확인하기 위해 해당 줄에 중단점 걸고 <F5>로 디버깅한다.
② <F11>로 `Factorial()`에 진입한다.
호출 스택에서 원하는 부분을 더블 클릭해서 선택하면 코드는 정지한 채 해당 부분(지역)의 상황을 보여준다.
팩토리얼을 반복문으로 표현할 때 여러 번 사용하거나 숫자가 달라질 때마다 일일이 변경해야 되는 번거로움이 있다.
여러 명이서 팀으로 코드를 공유할 때
ⓐ 팀원들이 필요할 때마다 반복문의 위치(어떤 cpp파일에 몇 번째 라인)를 알려주고 복사해서 사용하라고 한다.
ⓑ 값을 변경해야 될 때 반복문에서 해당하는 값을 매번 변경해줘야 한다.
Q. 번거로움을 없애려면 어떻게 해야 될까?
A. `Factorial()`이라는 이름의 함수를 만들면 된다.
값을 변경해야 될 때 `main()`에서 `Factorial()`를 호출하고 값을 바꿔서 넣어주면 된다.
(변수명에 왜 언더바(_)를 썼는지는 나중에 다룰 것이다.)
// 팩토리얼 함수
int Factorial(int _count)
{
int value = 1;
for (int b = 0; b < _count - 1; ++b)
{
value *= (b + 2);
}
return value;
}
int main()
{
int value = Factorial(3); // 6
value = Factorial(15); // 1307674368000
return 0;
}※`Factorial()`에 있는 `value` ≠ `main()`에 있는 `value`
함수가 종료되면 호출 스택에서 없어지는데, 팩토리얼 함수 안에 있는 변숫값은 어떻게 되는 걸까?
스택의 후입선출 구조로 `main()`보다 `Factorial()`가 나중에 들어왔기 때문에 `Factorial()`가 먼저 종료된다.(함수 스택이 사라진다.)
`Factorial()`가 종료되면 호출 스택에서 없어진다.
Q. 함수가 종료되면 함수에 있던 변숫값은 바로 사라질까? 아니면 값을 넘겨주고 사라질까?
A. 함수에 있는 변숫값은 해당 연산이 진행되는 동안에 존재했다가 연산이 끝나고 값을 넘겨주면 사라진다.
함수가 리턴될 때 CPU가 변숫값을 레지스터 메모리에 잠시 받아놨다가 연산이 진행 중이라면 다시 값을 꺼내와서 연산한다.
• 레지스터 메모리 : CPU에 내장되어 있으며, CPU가 연산할 때 임시로 빠르게 접근할 수 있는 메모리 영역이다.
일상생활에서 함수의 리턴값(전달값)을 물건 보관소에 맡겨놓는 것과 비슷하다.
2. 팩토리얼 ➜ 재귀함수
▷ 반복문으로 10!을 표현한 코드 vs. 팩토리얼을 되돌려주는 `F_Re()`
int Factorial(int _count)
{
int value = 1;
for (int b = 0; b < _count - 1; ++b)
{
value *= (b + 2);
}
return value;
}
// 재귀함수로 표현한 팩토리얼
// 탈출 조건이 없어서 계속 호출된다.
// 팩토리얼을 되돌려주는 `F_Re()`
// F = Factorial, Re = Recursive Function
int F_Re(int _count)
{
return _count * F_Re(_count - 1);
}
int main()
{
// Factorial()
int value = Factorial(10); // 3628800
// F_Re()
int value = F_Re(5);
return 0;
}
`F_Re()`처럼 탈출 조건을 걸지 않으면 끝없이 진행되기 때문에 오류가 발생한다.
① F_Re(5) = 5 x F_Re(4)
② F_Re(4) = 4 x F_Re(3)
③ F_Re(3) = 3 x F_Re(2)
④ F_Re(2) = 2 x F_Re(1)
⑤ F_Re(1) = 1 x F_Re(0)
⑥ F_Re(0) = 1 x F_Re(-1)
⋯
팩토리얼은 1부터 n까지의 자연수를 곱하는 것이므로 `F_Re(1)`일 때 1을 반환하면서 함수가 종료되어야 된다.
return을 만나면 함수 스택이 종료되므로 `return 1;`로 1을 return 한다.
▷ `_count`값이 1이면 1을 return 하는 부분을 추가한 코드
int F_Re(int _count)
{
// 탈출 조건
if (_count == 1)
{
return 1;
}
return _count * F_Re(_count - 1);
}
int main()
{
int value = F_Re(5); // 20
return 0;
}진행 순서는 아래와 같다.
① F_Re(5) = 5 x F_Re(4)
② F_Re(4) = 4 x F_Re(3)
③ F_Re(3) = 3 x F_Re(2)
④ F_Re(2) = 2 x F_Re(1)
⑤ F_Re(1) return값 : = 1
⑥ F_Re(2) return값 : 2 x 1 = 2
⑦ F_Re(3) return 값 : 3 x 2 = 6
⑧ F_Re(4) return 값 : 4 x 3 = 12
⑨ F_Re(5) return 값 : 5 x 4 = 20
∴ F_Re(5) = 20
▷ 재귀함수로 10!을 표현한 코드
int F_Re(int _count)
{
if (_count == 1)
{
return 1;
}
return _count * F_Re(_count - 1);
}
int main()
{
int value = F_Re(10); // 3628800
return 0;
}
팩토리얼 ➜ 반복문 vs. 재귀함수
// 반복문
int Factorial(int _count)
{
int value = 1;
for (int b = 0; b < _count - 1; ++b)
{
value *= (b + 2);
}
return value;
}
// 재귀함수
int F_Re(int _count)
{
if (_count == 1)
{
return 1;
}
return _count * F_Re(_count - 1);
}
int main()
{
// 반복문
int value = Factorial(10); // 3628800
// 재귀함수
int value = F_Re(10); // 3628800
return 0;
}피보나치 수열(Fibonacci Sequence)
1 1 2 3 5 8 13 21 34 55 ⋯
1 + 1 = 2
1 + 2 = 3
2 + 3 = 5
⋯
이런 식으로 바로 앞에 있는 2개의 숫자를 계속 더해나가면 된다.
편의상 0번째 항을 0으로 두기도 하지만, `0 1`로 시작해도 어차피 `1 1`부터 시작하기 때문에 시작점을 1로 잡았다.
피보나치 수열에서 n번째 숫자가 무엇인지 구하는 코드 (반복문, 재귀함수)
1. 피보나치 수열 ➜ 반복문
int Fibonacci (int _count)
{
// 첫 번째, 두 번째 숫자 : 1
if (_count == 1 || _count == 2)
{
return 1;
}
}세 번째 숫자인 2는 1번, 네 번째 숫자인 3은 2번 계산한다.
Q. 그렇다면 n번째 숫자는 몇 번 계산할까?
A. (n-2)번
▷ 예시
int Fibonacci (int _count)
{
if (_count == 1 || _count == 2)
{
return 1;
}
// n번째 숫자 : (n - 2)번 계산
for (int i = 0; i < _count - 2; ++i)
{
}
}① `1 1` → 2
② `1 2` → 3
③ `2 3` → 5
⋯
① 첫 번째 + 두 번째 = 1 + 1 = 2
2를 기준으로 바로 앞에 2개의 숫자를 더한다.
`1` + `1`
↓
`2`
② 두 번째 + 세 번째 = 1 + 2 = 3
`1` + `2`
↓
`3`
③ 세 번째 + 네 번째 = 2 + 3 = 5
`2` + `3`
↓
`5`
1. 변수 2개를 정한다.
Preview ➜ `p`로 표현하고 더하는 두 개의 값 중에 첫 번째 값을 `p1`, 두 번째 값을 `p2`로 놓자.
2. `p1`와 `p2`를 더한 값을 `value`에 넣는다.
`1 1`로 시작하기 때문에 `p1`, `p2`는 둘 다 1이다.
`p1` + `p2` → `value`
어떤 숫자에서 그다음 숫자를 구하려면 `value`가 `p2` 자리로 가야 한다. `p2`에 있던 값은 `p1`로 가야 한다.
`p1` ←② `p2`
①↗
`value`
▷ 수정한 코드
int Fibonacci (int _count)
{
if (_count == 1 || _count == 2)
{
return 1;
}
int p1 = 1;
int p2 = 1;
int value = 0;
for (int i = 0; i < _count - 2; ++i)
{
value = p1 + p2; // p1 + p2를 value에 넣는다.
p2 = value; // value를 p2에 넣는다.
p1 = p2; // p2를 p1에 넣는다.
}
return value;
}위의 코드처럼 작성하면 발생하는 문제
컴퓨터는 우리가 시킨 일만 한다.
5를 시작점으로 한 `5 8 13`으로 알아보자.
`5` + `8`
↓
`13`
그다음 숫자로 갈 때 어떤 문제가 발생할까?
`5` ←② `8`
①↗
`13`
① ➜ 13을 8이 있던 자리에 넣는다.
`5` ←② `13`
①↗
`13`
8이 5가 있던 자리에 들어가야 되는데 이미 13이 8을 덮어버렸기 때문에 8은 사라진다.
② ➜ 13이 5가 있던 자리에 들어간다.
`13` `13 `
`13`
어떻게 수정해야 될까?
`value`가 `p2`로 가고 `p2`가 `p1`으로 가기 때문에 `p1`은 덮어져도 된다.
8이 5가 있던 자리에 들어가고 13이 8이 있던 자리에 가야 된다.
▷ 수정한 코드
int Fibonacci (int _count)
{
if (_count == 1 || _count == 2)
{
return 1;
}
int p1 = 1;
int p2 = 1;
int value = 0;
for (int i = 0; i < _count - 2; ++i)
{
value = p1 + p2; // p1 + p2를 value에 넣는다.
p1 = p2; // p2를 p1에 넣는다.
p2 = value; // value를 p2에 넣는다.
}
return value;
}
int main()
{
int value = Fibonacci(3); // 2
return 0;
}
2. 피보나치 수열 ➜ 재귀함수
Q. n번째 숫자는 몇 번째와 몇 번째의 합일까?
A. (n-1) 번째와 (n-2) 번째의 합
▷ 피보나치 수열을 재귀함수로 표현한 코드
int Fibonacci_Re(int _count)
{
if (_count == 1 || _count == 2)
{
return 1;
}
return Fibonacci_Re(_count - 1) + Fibonacci_Re(_count - 2); // (n - 1)번째 숫자 + (n - 2)번째 숫자
}
int main()
{
int value = Fibonacci_Re(9); // 34
return 0;
}
피보나치 수열 ➜ 반복문 vs. 재귀함수
// 반복문
int Fibonacci (int _count)
{
if (_count == 1 || _count == 2)
{
return 1;
}
int p1 = 1;
int p2 = 1;
int value = 0;
for (int i = 0; i < _count - 2; ++i)
{
value = p1 + p2;
p1 = p2;
p2 = value;
}
return value;
}
// 재귀함수
int Fibonacci_Re(int _count)
{
if (_count == 1 || _count == 2)
{
return 1;
}
return Fibonacci_Re(_count - 1) + Fibonacci_Re(_count - 2);
}
int main()
{
// 반복문
int value = Fibonacci(7); // 13
// 재귀함수
int value = Fibonacci_Re(7); // 13
return 0;
}일반 재귀함수는 다음 재귀함수를 호출할 때 기존 함수의 정보를 저장해야 돼서 메모리 사용량이 많아 성능이 저하되는 문제가 발생한다.
이를 보완하고자 꼬리 재귀를 사용한다.
꼬리 재귀 (Tail Recursion)
여기서 꼬리의 의미는 함수에서 최종적으로 값을 리턴하는 곳을 말한다.
int Factorial(int n, int acc = 1) {
if (n == 0) return acc;
return Factorial(n - 1, n * acc); // 더 이상 연산이 없기 때문에 스택은 쌓이지 않는다.
}위의 코드처럼 재귀 호출을 해당 함수의 가장 마지막에 한다.
기존에 호출된 함수의 스택을 지속적으로 저장하지 않아서 메모리가 과도하게 쌓이는 것을 방지해 준다.
다시 말해서, 호출 후에는 더 이상 할 일이 없기 때문에 스택에서 이전 함수 호출을 추적할 필요가 없다.
컴파일러는 함수에 필요한 메모리를 줄이는 최적화를 수행하는데, 이때 꼬리 호출 최적화가 사용된다.
꼬리 호출 최적화(TCO, Tail Call Optimization)
C++에서 지원하는 기능으로, 컴파일러가 다음 재귀 함수 호출했을 때 기존 함수의 저장되어 있던 정보를 메모리에서 제거함으로써 재귀 함수의 동작을 최적화한다.
재귀 함수를 사용해도 일반 재귀에서처럼 추가적인 메모리의 사용이 사라졌기 때문에 결과적으로 메모리 사용량은 반복문과 비슷하다.
※ 주의
TCO를 지원하지 않는 언어는 꼬리 재귀 방식을 사용해도 일반 재귀 함수 방식으로 작동해서 스택 오버 플로우가 발생할 수 있다.
꼬리 호출 최적화 지원 언어 : C++, C#, Kotlin 등
꼬리 호출 최적화를 지원하지 않는 언어 : Java, Python 등
꼬리 재귀 방식을 사용한다고 해서 항상 TCO가 적용되는 것은 아니다.
TCO를 적용하지 않는 경우
int Factorial(int n){
if(n == 1)
return 1;
return n * Factorial(n - 1);
}이 경우 `n *`은 재귀 호출 후에 발생해서 각 호출은 `Factorial(n - 1)`의 결과를 기다리는데, 이때는 TCO를 적용할 수 없다.
'Programming Language > C++' 카테고리의 다른 글
| [C++] 구조체(Structure)[C++ vs. C], 구조체 포인터 (0) | 2024.03.08 |
|---|---|
| [C++] 배열(Array) (0) | 2024.03.04 |
| [C++] 반복문, 반복문 탈출 방법 (0) | 2024.03.03 |
| [C++] 입출력 (printf(), scanf(), cout, cin) (0) | 2024.03.03 |
| [C++] 함수[main()], return, void (0) | 2024.03.03 |