[알고리즘] 재귀함수

1. 재귀함수란?

• 재귀함수 (Recursion) 는 정의 단계에서 자신을 재참조하는 함수이다.
• 전달되는 매개변수(파라미터)만이 달라질 뿐 동작은 동일하다.

2. 주의사항

• 반드시 종료조건을 작성해야 한다. (안그러면 아래 만화처럼 된다.)
• 입력 값의 변화가 특정 패턴을 반복하면 안된다. (ex | f(a)가 f(b)를 호출한뒤 f(b)가 f(a)를 호출하는 구조같은, 이러면 무한히 반복되다가 콜스택 초과로 프로그램이 뻗는다.)

전형적인 종료조건이 없는 재귀함수 ㅋㅋㅋ
1. 내가 왜?
2. 미수 줄게 ㅇㅇ
3. 미수가 뭔데
4. 이걸 모름? 설명주절주절
3. 그래서 미수가 뭔데
4. 아니 이걸 모름? 설명주절주절
5. 내가 왜?

위와 같은 이유로 재귀함수에는 기저사례(종료 조건)이 필수로 들어가야 한다.

사실 반복문으로 해결가능한 문제는 반복문으로 해결하는게 가장 좋음

3. 재귀함수로 팩토리얼 구현하기

코드

int factorial(int number) {

    if (number == 1)
        return 1;
    else
        return number * factorial(number - 1);
}


int main() {

    int num;
    
    cout << "insert new number : " << "\n";
    cin >> num;

    int fact = factorial(num);

    cout << "factorial of " << num << " is: " << fact << "\n";

    return 0;

}

만약 factorial(5)를 호출한다고 가정해보자.

1. factorial(5) 호출한다.
2. number가 5이므로 if블록에서 걸러지지 않기 때문에, else 블록으로 들어감.
3. return 5 * factorial(number - 1) 실행. 여기서 factorial(number - 1)는 새로운 함수 호출 프레임을 스택 메모리에 추가하며 호출됨.
4. factorial(number - 1)의 호출이 완료되어 결괏값 4가 반환되고, 이를 이전 스택 프레임의 계산에 사용.
5. return 5 * 4 계산 완료, 결괏값 20 반환.
6. factorial(5)의 호출이 완료되어 최종적인 결과 20 반환.

3-1. 도식화

사실 글로 재귀함수를 설명하는 것은 잘 이해가 되지 않는다. 한번 도식화 해보자

우리는 main 함수를 통해 factorail함수에 대한 매개 값(number)으로 (5)를 받았다.
number는 1에 도달하게 되면 1을 리턴한다. (1의 팩토리얼은 1이기 때문)

그리고 재귀함수는 자기 자신을 호출하며 아래와 같이 동작한다.

1. factorial(5) = 5 * factorial(4)
2. factorial(4) = 4 * factorial(3)
3. factorial(3) = 3 * factorial(2)
4. factorial(2) = 2 * factorial(1)
5. factorial(1) = return 1

factorial(1) = 1 에 도달하면 재귀함수가 탈출하면서 동작하게 된다.

1. factorial(2) = 2 * 1 = 2
2. factorial(3) = 3 * 2 = 6
3. factorial(4) = 4 * 6 = 24
4. factorail(5) = 5 * 24 = 120

이상 끝.