재귀함수란?
자신이 자신을 호출하는 함수다.
논리 구조는 반복문과 같다.
반복을 끝내기 위한 조건을 신중히 생각해야 한다.
콜스택을 활용하기 위해 사용한다.
고급 정렬 알고리즘 및 트리 탐색과 함께 일반적으로 사용된다.
반복문보다 느리며 메모리를 더 많이 사용한다.
- Base case: 간단히 결과를 반환하는 부분
- Recursive case: 자기 자신을 호출하는 부분
팩토리얼
- 수학적 정의
- n = 0일 경우, n! = 1
- n > 0일 경우, n! = n x (n-1)!
1! = 1
2! = 2 x 1! = 2
3! = 3 x 2! = 3 x 2 = 6
4! = 4 x 3! = 4 x 6 = 24
5! = 5 x 4! = 5 x 24 = 120- 코드로 표현해보기
int factorial(int n) {
// base case
if (n == 0) {
return 0;
}
// recursive case
return n * factorial(n - 1);
}
코드의 실행단계를 살펴보자.
우선 스택 메모리에서 main이 실행된다.
실제 코드가 스택메모리에 올라오는 것은 아니고, 함수 실행에 필요한 변수들과 함수 호출이 일어났을 때 호출한 함수로 돌아가기 위한 return address가 저장된다.
factorial(0)까지 아무런 계산이 이루어지지 않는다. 왜냐하면 예를 들어 factorial(3)에서 factorial(2)의 결과값이 없기 때문이다.
factorial(0)에서 1을 반환하고, 다시 되돌아가며 계산이 이루어진다.
예시
우선 반복문의 경우 위처럼 작성한다.
반복문의 경우 콜스택을 살펴보면 main -> walk(5)로 표시된다.
반복문 함수를 호출하면 스택을 사용하기 때문에 LIFO 방식을 사용하므로 main 위에 walk(5)가 올라온다.
재귀함수로 작성하면 위처럼 작성한다.
재귀함수의 경우, 종료 조건을 만날 때까지 차례대로 스택을 쌓다가 종료 조건을 만나면 다시 돌아가며 마지막에 결과값을 반환한다.
만약 파라미터가 1억처럼 많이 크면 "stack overflow" 에러가 발생할 수도 있다.
return; VS return 1;
- return;
return;은 반환 타입이 void인 함수에서 사용된다. 즉 아무런 반환값이 없는 함수에서 사용한다.
함수의 실행을 종료하고 호출한 곳으로 제어를 돌려보내는 역할을 한다.
예를 들어, 어떤 조건을 만족하는 경우 재귀적 탐색을 중단하고 싶은 상황에서 사용할 수 있다.
void exampleFunction(int n) {
if (n == 0) {
return; // 더 이상의 처리 없이 함수를 종료
}
// 그 외의 경우에는 무언가 처리
exampleFunction(n - 1);
}- return 1;
return 1;은 함수가 int와 같은 특정 타입의 값을 반환해야 할 때 사용된다.
이 경우, 함수는 1이라는 정수 값을 반환하며, 반환 타입은 int여야 한다.
재귀 함수에서 return 1;을 사용하는 경우, 보통 재귀의 기본 경우(base case)에서 사용되며, 이는 재귀 호출의 연쇄를 종료하는 데 사용된다.
이 값은 재귀 호출의 결과에 영향을 미친다.
예를 들어, 팩토리얼을 계산하는 재귀 함수에서는 n == 0일 때 1을 반환하여, 팩토리얼의 정의에 따른 0! = 1을 만족시킨다.
int factorial(int n) {
if (n == 0) {
return 1; // 기본 경우, 0! = 1
}
return n * factorial(n - 1); // 재귀 호출
}
결론적으로, return;은 void 타입 함수에서 실행을 종료하고, return 1;은 값을 반환하는 함수에서 특정 값을 (1을) 반환하며 실행을 종료한다.
