Ch 09. 함수 - 02. 재귀 함수

1. 재귀함수

재귀 함수(recursive function)는 함수의 내부에서 자기 자신을 다시 호출하는 함수를 말한다.

void func() {
    func(); // 자기 자신을 다시 호출
}

이렇게만 구현하면 무한으로 자기 자신을 호출하기 때문에 반드시 종료조건(base case)을 만들어 줘야만 한다

 

재귀 함수를 사용하는 보통의 기본적인 구조는

반환형 함수이름(매개변수) {
    if (종료조건) {
        return 값;
    } else {
        return 자기자신을 호출;
    }
}

이런 형태로 항상 종료 조건 + 재귀 호출의 두가지 부분으로 구성되게 된다.

 

2. 재귀함수의 사용 예제

재귀 함수는 문제를 더 작은 문제로 나눠서 푸는 방식으로써 알고리즘에서는 중요한 개념이다

이 재귀함수를 사용하는 예제를 하나 씩 나열해 보면

 

1) 펙토리얼 구하기

재귀 함수를 사용하면 팩토리얼의 값을 쉽게 구할 수 있도록 구현이 가능하다.

팩토리얼이란 어떤 자연수 n이 있을때 n!(n팩토리얼)은 1부터 n까지의 모든 자연수를 곱한 값을 말한다.

2! = 2 * 1
3! = 3 * 2 * 1
4! = 4 * 3 * 2 * 1
...
n! = n × (n-1) × (n-2) × ... × 3 × 2 × 1

 

이걸 재귀함수로 만들어보자면 반환타입이 int인 팩토리얼이란 이름을 가진 함수를 만들어주고 

매개변수로는 숫자 하나를 받아주자.

이 상태에서 다시 팩토리얼에 대해서 생각해보면

2! = 2 * 1!
3! = 3 * 2!
4! = 4 * 3!

과 같은 형태로 분리도 가능하다는 것을 볼 수 있다.

이는 함수로 보자면

myFactorial(2) = 2 * myFactorial(1);
myFactorial(3) = 3 * myFactorial(2);
myFactorial(4) = 4 * myFactorial(3);

로 표현할 수 있게 된다.

이걸 n으로 구현해보면

myFactorial(n) = n * myFactorial(n-1);

로 구현을 하면된다는 것을 알 수 있다.

그리고 전달된 n이 1이 된다면 팩토리얼 연산의 종료 시점이라는 것을 알 수 있다.

myFactorial(n) = n * myFactorial(n-1);
myFactorial(n-1) = n * myFactorial(n-2);
....
myFactorial(2) = 2 * myFactorial(1);
myFactorial(1) = 1;

이걸 함수로 구현해보면

팩토리얼에 전달되는 전달인자가 1이 아니라면

전달된 인자를 자기 자신과 곱하면 되고 만약 전달된 n의 값이 1보다 작거나 같은 값이라면

1을 던지고 종료한다 라고 구현 되면 Factorial 함수의 정의가 종료된다.

 

한번 실행해보면

 

3!의 경우는

3 * 2 * 1 = 6

의 결과를 출력해줘야 한다

그러면 5!을 호출해보면

5 * 4 * 3 * 2 * 1 = 120

잘 출력되는 것을 볼 수 있다.

 

2) 피보나치 수열

이전에 for문을 사용해서 만들었던 피보나치 수열을 재귀함수를 사용해서 만들어보자.

피보나치 수열은 

1회 
-> 1

2회
-> 1

3회
-> 2회(1) + 1회(1)
-> 2

4회
-> 3회(2) + 2회(1)
-> 3

5회
-> 4회(3) + 3회(2)
-> 5

...

n회
-> n-1회 + n-2회

와 같이 늘어나는 수열을 말한다

이걸 함수로 만들어보면 먼저 동일하게 반환형 int, 매개변수 int를 하나 받는 피보나치 함수를 만들어주고

n회차에 해당하는 부분으로 

이렇게 n-1 회차와 n-2회차를 더해주자.

이렇게 더해나가다가 전달되는 n의 값이 2가 되면 2회차에 대한 값을 출력하게 되는건데 보면 

1회 
-> 1

2회
-> 1

3회
-> 2회(1) + 1회(1)
-> 2

...

 

2회차와 1회차는 1의 값을 고정적으로 반환하는 것을 볼 수 있다.

그렇다면 종료 조건은 n이 2일 혹은 1일때는 1을 반환하는 것이된다고 해석하면

이렇게 구현함으로써 피보나치 수열이 완성 된다.

 

미리 회차에 따른 피보나치 수열을 나열해보자면

1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 ...
1 , 1 , 2 , 3 , 5 , 8, 13, 21, 34 ..

이렇게 10회차의 결과와 2, 1 회차의 결과도 정확하게 나오는 것을 볼 수 있다.

 

3) Node의 순회

Node의 경우는 예를 들어 트리 구조

       1
      / \
     2   3
    / \
   4   5

와 같은 트리가 존재한다고 했을때 이 노드를 순회하는 것을 볼 텐데 

 

노드의 순회 방법은 세가지 방법이 있다.

순회명	순회 방식	설명
전위순회(Preorder Traversal)	루트 → 왼쪽 서브트리 → 오른쪽 서브트리	root → left → right
중위순회(Inorder Traversal)	왼쪽 서브트리 → 루트 → 오른쪽 서브트리	left  → root→ right
후위순회(Postorder Traversal)	왼쪽 서브트리 → 오른쪽 서브트리 → 루트	left → right → root

 

이 노드를 코드로 구성한다면 구조체를 사용해서 Node라는 구조체를 만들어서 확인을 해야한다.

여기서 val은 각 노드가 가진 값들을 말하고 left, right는 각 노드의 왼쪽과 오른쪽 노드를 말한다

여기서 왼쪽, 오른쪽 노드를 Node포인터로 선언한 이유는 Node를 정의한 곳에서 Node를 선언할 수는 없기 때문이다

만약 이렇게 구조체 내부에 같은 구조체를 선언하면 이 Node라는 구조체는 무한한 크기의 구조체가 되게 된다(Node안에 Node 안에 Node안에... 무한히 중첩되는 구조가 생성)

 

그렇기에 이 Node라는 구조체를 정의할때 Node라는 타입을 사용한다면 Node포인터를 사용해서 넣어주면 포인터는 주소값을 저장하는 형태이기에 고정된 값을 지니기에 문제가 없어진다.

 

그래서 Node의 멤버로 Node타입을 넣기 위해 Node 포인터를 사용해서 left와 right 노드를 추가한 것이다.

 

이제 순회에 대해서 각각 알아보도록 하자

 

*전위 순회

** 1회차 순회: root(1) : 방문 완료 1
        1 ← 1
       / \
      2   3
     / \
    4   5
   
** 2회차 순회: root 기준 왼쪽이 존재하기에 left(2) : 방문 완료 2
        1 
       / \
  2 → 2   3
     / \
    4   5
   
** 3회차 순회: 2 기준 왼쪽이 존재하기에 left(4) : 방문 완료 4
        1 
       / \
      2   3
     / \
3 → 4   5

** 4회차 순회: 4 기준 왼쪽도 오른쪽도 존재하지 않기에 상위의 right(5) : 방문 완료 5
        1 
       / \
      2   3
     / \
    4   5  ← 4
    
** 5회차 순회: 5 기준 왼쪽도 오른쪽도 존재하지 않기에 2 -> 1로 가서 오른쪽이 존재하기에 right(5) : 방문 완료 3
        1 
       / \
      2   3 ← 5
     / \
    4   5  
    
최종 전위순회 결과: 1 → 2 → 4 → 5 → 3

 

이를 이해하려면 코드로써 생각을 해봐야 한다.

회차와 방문 완료의 개념에 대해서 코드로 보자면 

 

먼저 방문이란 개념을 위한 visit함수하나 선언해주고

이는 순회중 순서대로 결과를 출력하기 위한함수로 사용될것이다.

그리고 전위순회의 함수는

이런식으로 구성된다 

root -> left -> right로

root를 만나면 visit완료 되었다고 확인되며 숫자를 반환해준다.

그리고 left로 가서 다시 visit이 완료 되었다고 출력 되며 만약 리프노드(마지막 끝에 있는 node)를 만난다면 그 위 단계로 복귀하는 식이다.

 

노드를 생성해주고 

이제 전위순회 재귀함수를 호출해주면

이렇게 전위순회의 결과를 출력한다.

 

*중위 순회

** 1회차 순회: root(1)의 왼쪽이 존재 left(2) 
         1
        / \
   1 → 2   3
      / \
     4   5
   
** 2회차 순회: 2 기준 왼쪽이 존재 left(4) 
         1 
        / \
       2   3
      / \
 2 → 4   5
   
** 3회차 순회: 4 기준으로 왼쪽 노드가 존재하지 않음(리프노드) : 순회완료(4)
         1 
        / \
       2   3
      / \
3 → [4]   5

** 4회차 순회: 4의 root(2)로 back : 순회완료(2)
         1 
        / \
  4 → [2]   3
      / \
     4   5
    
** 5회차 순회: root(2) 기준으로 right(5) 방문 : 순회완료(5)
        1 
       / \
      2   3 
     / \
    4  [5]  ← 5
    
** 6회차 순회: 5 기준으로 왼쪽 없음/ 왼쪽없음 2 -> 1로 back 했을때 root(1) 방문 : 순회완료(1)
       [1]  ← 6
       / \
      2   3 
     / \
    4   5
    
** 7회차 순회: root(1) 기준으로 right(3) 방문
        1 
       / \
      2   3 ← 7 
     / \
    4   5  
    
** 8회차 순회: root(3) 기준으로 왼쪽이 없기에 right(3) 방문 : 순회완료(5)
        1 
       / \
      2  [3] ← 8
     / \
    4   5  
    
최종 중위순회 결과: 4 → 2 → 5 → 1 → 3

중위 순회에서도 Node 구조체와 visit함수를 그대로 사용하고

전위 순회에서 순회 순서만 변경해서 left -> root -> right 순으로 

이렇게 선언해주고 호출해주면

이렇게 중위 순회를 하게 된다

 

*후위 순회

** 1회차 순회: root(1)의 왼쪽이 존재 left(2) 
         1
        / \
   1 → 2   3
      / \
     4   5
   
** 2회차 순회: 2 기준 왼쪽이 존재 left(4) 
         1 
        / \
       2   3
      / \
 2 → 4   5
   
** 3회차 순회: 4 기준으로 왼쪽, 오른쪽 노드가 존재하지 않음(리프노드) : 순회완료(4)
         1 
        / \
       2   3
      / \
3 → [4]   5

** 4회차 순회: 4의 root(2)로 back, 오른쪽 노드가 존재 right(5) 방문
         1 
        / \
  4 →  2   3
      / \
     4   5
    
** 5회차 순회: 5의 왼쪽, 오른쪽 노드가 존재하지 않음 : 순회완료(5)
        1 
       / \
      2   3 
     / \
    4  [5]  ← 5
    
** 6회차 순회: 5 -> 2로 back 했을때 왼쪽, 오른쪽 노드 모두 방문했기에 root(2) 순회 : 순회완료(2)
        1 
       / \
  4 →[2]  3 
     / \
    4   5
    
** 7회차 순회: 3의 왼쪽, 오른쪽 노드가 존재하지 않음 : 순회완료(3)
        1 
       / \
      2  [3] ← 7 
     / \
    4   5  
    
** 8회차 순회: 3 -> 1로 back, 마지막 root(1)의 순회 : 순회완료(1)
       [1] ← 8
       / \
      2   3 
     / \
    4   5  
    
최종 중위순회 결과: 4 → 5 → 2 → 3 → 1

 

동일하게 코드에서 Node 구조체와 visit함수는 유지한 채로 

순회 조건만 left → right → root 순으로 변경

결과를 보면

로 우리가 예상한 결과가 나오는 것을 볼 수 있다.

 

제귀 함수에 연결되는 부분으로 분할, 탐색, 백트래킹, 트리/그래프 순회와 관련된 알고리즘에서는 재귀함수를 많이 사용하게 된다.

 

재귀함수가 사용될 수 있을 만한 알고리즘에 대해서 아래와 같이 나열 했으니 추후 공부해보는것도 좋을것으로 보인다.

• 수학적 계산 - 팩토리얼, 피보나치 수열, 최대공약수(GCD), 거듭제곱 등
• 분할 정복 - 병합정렬(Merge sort), 퀵 정렬(Quick sort), 이진 탐색 등
• 트리탐색 - 전위/중위/후위 순회, 높이 구하기, 노드 개수 세기 등
• 그래프 탐색 - DFS(깊이 우선 탐색), 백트래킹 등
• 백트래킹 - N-Queen 문제, 미로 찾기, 조합/순열 생성 등
• 기타 - 하노이의 탑, 괄호 생성, 회문 검사, 문자열 뒤집기, 구조체 깊이 탐색