학습 일자 : 2023.

Recursion(재귀)

어떠한 것을 정의할 때 자기 자신을 참조하는 것

재귀함수의 조건

1. 함수내용 중 자기자신함수를 다시 호출해야함
2. 반드시 종료 조건이 있어야 함 → 없으면 무한히 자신을 호출하는 무한 루프에 빠질 수 있음

[재귀 함수 예시]

int Factorial(int x)
{
	if (x == 1) //종료 조건
		return 1;
	else { return x * Factorial(x - 1); } //자신을 다시 호출함
}

⇒ 재귀 함수는 함수 종료 후 재귀함수 호출 바로 다음 줄로 돌아온다는 것을 주의해야 함!

return x * Factorial(x - 1); 는 풀어 쓰면, 다음과 같이 쓸 수 있음.

int Factorial(int x)  // (0)
{
    Console.Write($"{x} >> "); // (1)
    if (x == 1) 
		{  // (2)
			Console.WriteLine(); 
			return 1; 
		}            
    else 
    {                                    // (3)
        int num = Factorial(x - 1);      // (4)
        Console.WriteLine($" x : {x} \\t Factorial(x - 1) : {num}"); //(5)
        return num * x;                  // (6)
    }
}

[output]

| 10 >> 9 >> 8 >> 7 >> 6 >> 5 >> 4 >> 3 >> 2 >> 1 >> x : 2 Factorial(x - 1) : 1 x : 3 Factorial(x - 1) : 2 x : 4 Factorial(x - 1) : 6 x : 5 Factorial(x - 1) : 24 x : 6 Factorial(x - 1) : 120 x : 7 Factorial(x - 1) : 720 x : 8 Factorial(x - 1) : 5040 x : 9 Factorial(x - 1) : 40320 x : 10 Factorial(x - 1) : 362880

[호출 순서] 0 → 1 → 3 → 4 → 0 → 1 → 2 → 3 → 4 → 0 … x가 1이 될 때까지 반복, x가 1이 되면 2번으로 이동 = 더 이상 자신을 호출 하지 않음 → 재귀함수 루프 종료

→ 루프 종료 후 재귀함수 호출 다음 위치(5번)로 돌아와 남은 작업을 수행함. (재귀함수 호출 횟수만큼 반복)

→ 남은 작업이 출력과 x값 리턴이기 때문에 함수 종료 후 x 값은 1이 아닌 10이 됨.

<aside> 💡 재귀 함수는 문을 열고 들어가는 작업임

→ 문을 열고 끝까지 들어갔으면, 작업 종료 후 하나 하나 다시 문을 닫으며서 나와야 함.

</aside>