재귀(Resursion)란?
재귀(Recursion)란?
- 위키에 따르면 자신을 정의할 때 자기자신을 재참조 하는것을 뜻하며 이를 프로그램에 적용한 재귀호출(Recursive Call)의 형태로 많이 사용된다고 한다.
재귀호출(Recursive Call)이란?
- A함수를 정의할 때 A함수 코드 내부에 나 자신(A함수)를 다시 호출하는것을 말한다.
void Recursive(){
printf("Recursive Call\n");
Recursive(); // 재귀호출
}재귀함수(Recursive Function)란?
- 함수 내에서 자기자신을 다시 호출하는 함수를 말한다.
void Recursive(){ // 재귀함수
printf("Recursive Call\n");
Recursive();
}
재귀함수의 동작 원리
- 재귀함수의 동작 원리를 그림으로 간단히 표현하면 아래와 같다.
실제 위 코드를 디스어셈블해서 살펴보면 아래와 같다.
위 <디스어셈블> 사진을 살펴보면 printf 함수 호출 후 call c_test.851014 와 같은 명령어를 실행한다는 것을 볼 수 있다. 그리고 명령어 오른쪽 코멘트 부분을 살펴보면 C_TEST.c:5 라고 되어있는데 이는 C_TEST.c파일의 5번째 줄을 의미한다. <테스트 코드>를 살펴보면 5번째 줄에 있는 코드는 Recursive() 함수를 재귀호출하는 부분임을 알 수 있으며 <디스어셈블> 사진 속 851014 주소로 가보면 아래와 같이 Recursive 함수로 점프하는 것을 알 수 있다.
즉, 실제 컴파일된 파일도 마찬가지로 내부적으로 위 <재귀함수의 동작 원리>의 그림대로 동작한다는 것을 알 수 있다. 그러나 위 코드를 실행시켜보면 잘 동작하다가 Stack overflow 오류가 발생한다.
Stack overflow는 프로그램 내부에서 사용하는 스택(쉽게 말해서 특정 값들을 저장하기 위한 공간)의 크기보다 데이터가 많이 저장되어 발생하는 오류인데, 원인은 프로그램의 구조를 알면 이해할 수 있다.
위 <테스트 코드>를 이용해 간단히 설명하자면 프로그램은 함수(Recursive) 내부로 들어가게 되면 함수 호출 전 데이터들(함수의 지역변수, 호출이 완료되고 다시 돌아갈 주소 등)을 스택에 저장하게 되는데, 위 코드의 경우 함수가 종료되는 조건이 없기 때문에 무한루프를 돌게 된다. 따라서 계속해서 데이터들을 스택에 저장하게 되고 무한루프를 돌면서 저장된 데이터들의 크기가 일정 크기를 넘어가게 되면서 스택 오버플로우가 발생하게 된 것이다.
이러한 문제를 해결하기 위해서는 재귀함수엔 무조건 재귀함수를 탈출할 수 있는 조건이 있어야 한다. 그 코드는 아래와 같다.
위 코드를 간단히 설명하면 if (n == 0) 의 조건과 Recursive 함수의 파라미터로 n값을 받도록 코드를 수정하였고, 따라서 5번만 Recursive Call을 실행한 후 동작이 완료된다.
위 <테스트 코드2>를 직접 비주얼 스튜디오에서 디버깅하면서 확인해보면 쉽게 알 수 있다.
'0x00. 자료구조' 카테고리의 다른 글
| 단순 연결 리스트 (0) | 2021.10.11 |
|---|---|
| 순차 리스트 (0) | 2021.10.06 |
| 공간복잡도(Space Complexity)란? (0) | 2021.05.05 |
| 시간복잡도(Time Complexity)란? (0) | 2021.04.30 |
| 자료구조란? (0) | 2021.04.25 |
