[알고리즘 - 기초] 재귀 함수 (Recursive Function)

재귀함수란 무엇인가?

---

자기 자신을 호출하는 함수를 재귀함수(Recursive Function)라고 하며 이때 하는 호출을 재귀호출(Recursive Call)이라고 한다.

팩토리얼, 하노이 탑과 같은 문제에서 많이 사용된다.

 

 

 

재귀 함수의 장점

---

• 직관적이며 간단하게 구현할 수 있다.
• 깊이 우선 탐색, 백트래킹, 분할 정복 등 많은 알고리즘에서 사용되기도 해서 기초가 되는 개념이다.

 

 

 

재귀 함수의 단점

---

• 재귀함수의 종료 조건을 잘 설정해주지 않으면 재귀함수를 빠져나오지 못하게 되면서 무한루프에 빠질 수 있다.
• 재귀 호출의 깊이가 너무 깊어지면 너무 많은 메모리를 사용한다.
• 불필요한 반복 연산을 하게 될 가능성이 있다.

 

 

 

팩토리얼 문제 재귀함수로 해결하기

---

팩토리얼을 구하는 함수가 있다고 생각해보자.

5팩토리얼을 재귀적으로 생각해본다면 아래와 같은 과정을 거친다.

 

5!

5 x 4!

5 x 4 x 3!

5 x 4 x 3 x 2!

5 x 4 x 3 x 2 x 1!

 

이것을 재귀 방정식으로 나타낸다면 다음과 같다.

 

여기서 1!은 더이상 재귀 호출을 해주지 않아도 되기 때문에 이 조건에서 재귀 호출을 종료해주면 된다.

이것을 시각적으로 표현한다면 아래와 같이 나타낼 수 있다.

 

 

 

 

문제 해결을 위해 백준 10872번 팩토리얼 문제를 풀어보자.

 

10872번: 팩토리얼

 

C 언어

#include <stdio.h>

int factorial(int n)
{
    if(n <= 1) return 1;
    else return n * factorial(n - 1);
}

int main()
{
    int n;

    scanf("%d", &n);
    printf("%d", factorial(n));
    return 0;
}

 

C++

#include <iostream>
using namespace std;

int factorial(int n)
{
    if(n <= 1) return 1;
    else return n * factorial(n - 1);
}

int main()
{
    int n;

    cin >> n;
    cout << factorial(n);

    return 0;
}

 

Python3

def factorial(n):
    if n <= 1:
        return 1
    
    else:
        return n * factorial(n - 1)

n = int(input())
print(factorial(n))

 

Java

import java.util.Scanner;

public class Main {
    static int factorial(int n)
    {
        if(n <= 1) return 1;
        else return n * factorial(n - 1);
    }

    public static void main(String[] args) {
        int n;
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        System.out.println(factorial(n));

        sc.close();
    }
}

 

 

피보나치 수열 문제를 재귀함수로 풀어본다면?

---

재귀함수의 단점을 극적으로 보여줄 수 있는 문제가 피보나치 수열이다.

 

피보나치 수열이란 0번째항은 0, 1번째항은 1, 그 뒤쪽의 항들은 바로 앞의 두 항을 더한 값을 가지는 수열을 말한다.

수식으로 나타낸다면 아래와 같다.

 

그럼 값이 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ....와 같이 이어질 것이다.

 

 

피보나치 수열을 재귀함수로 구현한다면 아래와 같이 될 것이다.

 

 

5번째 피보나치 수열을 구하기 위해 2번째 피보나치 수열을 3번 구해야한다. 그리고 1번째 피보나치 수열은 5번 호출한다.

만약 10,000번째 피보나치 수열을 구한다면 호출 횟수는 기하급수적으로 많아질 것이다.

 

피보나치 수열 문제는 동적 계획법(DP, Dynamic Programming)을 통해 해결할 수 있다.