재귀함수

재귀함수

🤖 재귀함수란?

• 함수 내에서 자기의 함수를 다시 호출하는 함수
• 스택 내에 차곡차곡 쌓아두었다가 일괄로 처리한다.

#include <stdio.h>

int func(int num) {
    if (num == 1)
        return 1;
    else 
        return num * func(num - 1);
}

void main() {
    int i;
    for (i = 5; i >= 0; i--) {
        if (i % 2 == 1)
            printf("func(%d) : %d\n", i, func(i));
    }
}

1. 첫번째 반복

• func(5) 호출
  - func(5)는 5 * func(4)를 반환

  • 이때, func(4)를 계산하기 위해 재귀 호출이 발생한다.

• func(4) 호출

• func(3) 호출

• func(2) 호출

• func(1) 호출 -> return 1;

• 재귀 반환 과정:

func(1)이 1을 반환하면 func(2)는 "2 * 1 = 2"를 반환한다.
func(2)가 2를 반환하면 func(3)는 3 * 2 = 6을 반환한다.
func(3)가 6을 반환하면 func(4)는 4 * 6 = 24를 반환한다.
func(4)가 24를 반환하면 func(5)는 5 * 24 = 120을 반환한다.

• printf("func(5) : %d\n", i, func(i));는 func(5) : 120을 출력한다.

2. 두번째 반복
   i % 2 == 1 조건이 거짓이므로 아무 것도 출력하지 않음

3. 세번째 반복
   func(3)의 결과를 출력한다.
   첫번째 반복때와 똑같이 스택을 사용하여 재귀호출을 한다.
   (첫번째 반복할 때 사용했던 스택을 재사용하고 그러지는 않는다.)

4. 네 번째 반복
   i % 2 == 1 조건이 거짓이므로 아무 것도 출력하지 않음

5. 다섯 번째 반복
   func(1)의 결과를 출력한다.

6. 최종 결과

func(5) : 120
func(3) : 6
func(1) : 1

중복 재귀함수