재귀 함수
-
함수 안에서 자기자신을 또 호출함
-
호출스택을 잘 봐야됨 --> 이걸 잘 활용해야 문제를 빨리빨리 찾을 수 있음
함수 복습
-
함수가 호출되면 일정한 영역을 생성하고 그 영역안에 선언된 변수는 지역변수
-
그리고 함수들이 호출되는 메모리 영역 전체는 stack memory 영역이라고 함 (선입후출이기 때문, 가장 먼저 호출된 main 함수가 가장 나중에 종료됨)
호출스택, 로컬, 조사식 (visual studio)
-
호출스택은 함수들이 어떻게 호출되고 종료 후 사라지는지를 보여줌
-
로컬은 현재 선언되고 초기화되고 있는 변수들을 보여줌
-
조사식은 로컬에서 보여주는 변수들 외에도 a + b 등의 내가 보고싶은 것도 설정해줄 수 있음
-
호출스택에서 원하는 함수를 더블클릭하면 그쪽 영역의 상황을 보여줌, 현재 시점이 Factorial 함수를 보여주고 있는데 main을 더블클릭하면 main으로 옮겨감
함수의 return 값을 불러오는 과정
-
int a = Factorial(num);이런 코드가 있을 경우 일반적으로는 return값을 건네주고 호출스택이 사라졌다고 생각할 수 있음 -
하지만 사실은 CPU가 연산값을 레지스터 메모리에 잠시 저장해두고 호출스택이 사라진 뒤 main 함수에서 레지스터 메모리의 값을 꺼내오는거임
이제 이걸 다 이해했으면 재귀함수를 이해할 수 있음
재귀함수의 원리
-
Factorial이 호출되면 스택이 생겨남, 거기서 막 연산을 하다가 return 하기전에 자기자신을 만나면?
-
새로운 Factorial 영역이 또 생겨남 (스택안에 스택이 마트료시카처럼 계속 생겨나는게 아니라 아예 별개의 영역이 생겨남) --> 그럼 거기서 또 막 연산을 하다가?
-
또 다른 스택이 생기고... 다시 연산하고.... 반복함
-
간단히 말하면 A함수 인에서 B함수를 호출하고 B함수 안에서 C함수를 호출하고.... 이 과정이 그저 전부 A함수일 뿐임
-
만약 이렇다면 C함수가 종료되고 return 하면 B함수로 돌아올거고, B가 끝나면 A로 돌아올거고.... 이거랑 똑같음
-
A1에서 A2를 부르고, A2에서 A3를 부르고... 하다가 A3가 끝나면 A2로, A2가 끝나면 A1으로 이게 재귀함수임
-
근데 문제는 이렇게 호출만 하다가 스택 메모리 영역을 오버한다? --> 그럼 그때 발생하는 오류가 stack overflow!
-
따라서 탈출 조건을 지정해야함
재귀함수 사용이유
- 가독성이 좋고 구현이 용이함
단점
-
성능이 매우 떨어짐 --> 여러번의 함수를 호출해서 각각의 함수에 남아있는 값들을 마치 현재의 지역변수처럼 사용하기 때문에 성능이 저하됨
-
(하나의 함수에서 여러개의 변수를 선언하는 것보단 당연히 성능이 떨어질 수 밖에 없음)
