[C# Basics] 재귀 함수

재귀 함수란?

재귀 함수는 자기 자신을 호출하는 프로그래밍 기법이다. 재귀 함수는 복잡한 문제를 더 작은 하위 문제로 나누어 해결할 수 있도록 도와준다.

재귀함수 기본 구조

재귀함수는 두 가지 주요 부분으로 구성된다.

1. 기저 조건(Base Case): 함수가 더 이상 자기 자신을 호출하지 않고 종료되는 조건.
2. 재귀 단계(Recursive Step): 함수가 자기 자신을 호출하는 단계.

피보나치 수열 재귀 함수 예시

*피보나치 수열이란? 

피보나치 수 - 위키백과, 우리 모두의 백과사전

기초적인 재귀함수의 예로, 피보나치 수열을 구하는 함수를 살펴보자.
피보나치 수열은 다음과 같이 정의된다.

• 첫 번째 수는 0이다.
• 두 번째 수는 1이다.
• 그 이후의 수는 바로 앞 두 수를 더한 값이다.

즉 수열은 0,1,1,2,3,5,8,13,... 이렇게 진행된다.
이 피보나치 수열의 n번째 수를 구하는 재귀함수를 C# 코드로 작성하면 다음과 같다.

public int Fibonacci(int n)
{
    if (n <= 1) // 기저 조건: n이 0 또는 1인 경우
        return n;
    else
        return Fibonacci(n - 1) + Fibonacci(n - 2); // 재귀 단계
}

•  기저 조건(Base Case): 'n'이 0또는 1인 경우, 그대로 'n'을 반환한다.
  'n == 0' 이면 '0'을 반환
  'n == 1' 이면 '1'을 반환
• 재귀 단계(Recursive Step): 'n'이 1보다 큰 경우, 피보나치 수열의 정의에 따라 'n-1'번째와 'n-2'번째의 수를 재귀적으로 구하여 더한 값을 반환한다.

그럼 위 함수로 피보나치 수열의 5번째 수를 구해 보자.

• Fibonacci(5)는 Fibonacci(4) + Fibonacci(3)을 호출.
  • Fibonacci(4)는 Fibonacci(3) + Fibonacci(2)를 호출.
    • Fibonacci(3)는 Fibonacci(2) + Fibonacci(1)를 호출.
      • Fibonacci(2)는 Fibonacci(1) + Fibonacci(0)을 호출.
        • Fibonacci(1)는 1을 반환.
        • Fibonacci(0)은 0을 반환.
      • 따라서, Fibonacci(2)는 1 + 0 = 1.
      • Fibonacci(1)는 1을 반환.
    • 따라서, Fibonacci(3)는 1 + 1 = 2.
    • Fibonacci(2)는 1을 반환.
  • 따라서, Fibonacci(4)는 2 + 1 = 3.
  • Fibonacci(3)는 2를 반환.
• 따라서, Fibonacci(5)는 3 + 2 = 5이다!

호출 과정 요약

 

Fibonacci(5)
= Fibonacci(4) + Fibonacci(3)
= (Fibonacci(3) + Fibonacci(2)) + (Fibonacci(2) + Fibonacci(1))
= ((Fibonacci(2) + Fibonacci(1)) + (Fibonacci(1) + Fibonacci(0))) + ((Fibonacci(1) + Fibonacci(0)) + Fibonacci(1))
= (((Fibonacci(1) + Fibonacci(0)) + Fibonacci(1)) + ((Fibonacci(1) + Fibonacci(0)) + Fibonacci(1)))
= (((1 + 0) + 1) + ((1 + 0) + 1))
= (1 + 1) + (1 + 1)
= 2 + 2
= 4

전체 출력 코드

class Program
{
    static void Main(string[] args)
    {
        Console.WriteLine(Fibonacci(5)); // 5
        Console.WriteLine(Fibonacci(7)); // 13
        Console.WriteLine(Fibonacci(10)); // 55
    }

    public static int Fibonacci(int n)
    {
        if (n <= 1)
            return n;
        else
            return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

직접 코드를 타이핑 해 보며 한줄 한줄 이해해 보시길 바란다.
이번에는 우리가 이전 포스팅에서 구현해 보았던 DFS 재귀 함수의 로직을 이해해 보자.

DFS 재귀함수

https://nybot-house.tistory.com/115

[자료구조C#] 그래프 - DFS (깊이 우선 탐색) 코드 구현

public void DFS(int here)
{
    Console.WriteLine(here); // 현재 정점 출력
    visited[here] = true; // 현재 정점을 방문했음을 표시

    for(int next = 0; next < adj.GetLength(0); next++) // 모든 정점을 순회
    {
        if (adj[here, next] == 0) // 연결되어 있지 않으면 스킵
            continue;
        if (visited[next]) // 이미 방문한 정점이면 스킵
            continue;
        DFS(next); // 연결된 정점을 재귀적으로 방문
    }
}

DFS 재귀함수 동작 과정 

DFS 탐색을 제니(1번)에서 시작한다고 가정.

graph.DFS(1);

1. 제니(1) 방문:

• here = 1
• Console.WriteLine(1) 출력: 1
• visited[1] = true
• 제니(1)와 연결된 정점을 순회: 카리나(0), 지수(2), 수지(3)

 

2. 카리나(0) 방문

• here = 0
• Console.WriteLine(0) 출력: 0
• visited[0] = true
• 카리나(0)와 연결된 정점을 순회: 제니(1), 수지(3)
• 제니(1)는 이미 방문했으므로 스킵
• 수지(3)를 재귀적으로 방문

3. 수지(3) 방문

• here = 3
• Console.WriteLine(3) 출력: 3
• visited[3] = true
• 수지(3)와 연결된 정점을 순회: 카리나(0), 제니(1), 아이린(4)
• 카리나(0)와 제니(1)는 이미 방문했으므로 스킵
• 아이린(4)를 재귀적으로 방문

4. 아이린(4) 방문

• here = 4
• Console.WriteLine(4) 출력: 4
• visited[4] = true
• 아이린(4)와 연결된 정점을 순회: 수지(3), 원영(5)
• 수지(3)는 이미 방문했으므로 스킵
• 원영(5)를 재귀적으로 방문

5. 원영(5) 방문

• here = 5
• Console.WriteLine(5) 출력: 5
• visited[5] = true
• 원영(5)와 연결된 정점: 아이린(4)
• 아이린(4)는 이미 방문했으므로 스킵
• 더 이상 방문할 정점이 없으므로 종료하고 이전 호출로 돌아감

6. 탐색 종료

7. 다시 처음 DFS(1) 로직으로 돌아가서 함수 실행. ->  DFS(2) 실행, 종료.

이 과정을 통해 그래프의 모든 연결된 정점을 깊이 우선으로 탐색하게 된다. 재귀 호출이 끝나면 이전 호출로 돌아가고, 모든 가능한 경로를 탐색한다.

재귀함수의 장점

간결함: 코드가 더 직관적이고 간결해진다.

문제 분할: 복잡한 문제를 더 작은 문제로 나누어 해결 가능하다.

단점

스택 오버플로우: 너무 많은 재귀 호출이 발생하면 스택 오버플로우가 발생할 수 있다.

성능: 재귀 호출은 반복문에 비해 성능이 떨어질 수 있다.