[Algorithm][Recursive]재귀 함수

추상적 자료형(Abstract data type)과 자료구조(Data structure)는 엄밀히 말하면 다르다.

가령 스택의 경우는 추상적 자료형이다. 그 이유는 리스트(List)는 정의만 존재하고 구현은 사용자 마음이다.

그러나 만약 누군가가 연결리스트(Linked List), 혹은 배열리스트(Array List, Vector)를 말한다면 그건 자료구조인 셈이다.

그러나 이런 구분이 애매한 녀석들도 존재하기는 한다.

스택(Stack)같은 녀석이 그 정체인데 스택은 추상적 자료형으로 분류되는게 맞으나 사실상 자료구조라고도 볼 수 있다.

왜냐하면 스택을 구현하는 방식이 배열과 연결리스트 두가지가 존재하긴 하지만 사실상 무조건 배열을 쓰는게 이득이기 때문이다.

그래서 필자의 포스팅에서는 추상적 자료형과 자료구조를 엄밀히 구분하지 않고 모두 자료구조라 논하겠다.

참고:

이 사이트의 예제 문제는 백준 사이트(https://www.acmicpc.net/)를 참조합니다.

예제:

백준 팩토리얼(10872)

재귀 함수는 자기자신을 호출하는 함수를 의미한다. 자기 자신을 호출하기 때문에 항상 무한루프의 위험성에 노출되어있다.

하지만 재귀 함수는 알고즘에서 많이 쓰이는 테크닉이면서 더 넘어가서 알고리즘이라는 분야를 넘어서도 많이 쓰인다.

재귀 함수를 쓰는 것은 재귀함수를 지원해주는 언어에서 사용할 수 있는 것이다.

사실 대부분의 언어가 재귀함수를 지원하기 때문에 지원하지 않는 언어를 먼저 찾아봐야할 것이다.

몇가지를 알고있었는데 기억이 나지 않는다... 여러분은 사용하는데 별 지장이 없을 것이다.

재귀함수를 알고리즘에 구현하는 예는 너무너무 많지만 간단한 예시를 보도록 하겠다.

가장 간단한 예로는 팩토리얼을 구하는 예제를 보도록 하자.

#include <stdio.h>

int N;

int f(int n) {
    if (n == 1) {
        return 1;
    }
    return n * f(n - 1);
}

int main() {
    scanf("%d", &N);
    printf("%d\n", f(N));
    return 0;
}

여기서 f라는 함수는 팩토리얼을 구하는 함수이다.

재귀함수를 자세히 보면 크게 두가지 부분이 중요하다.

int f(int n) {
    if (n == 1) {
        return 1;
    }
    return n * f(n - 1);
}

재귀함수는 자칫 잘못하면 영원히 무한루프에 빠질 수 있다.

그러므로 반드시 끝나는 상황을 지정해 주어야한다.

이러한 것을 Base Case라고 부른다.

위의 경우 n은 1씩 작아지기 때문에 언젠가는 반드시 1에 도달하여 멈추게 된다. (n은 양수를 넣어야한다.)

알고리즘에서 여러가지에서 많이 쓰인다. 백트래킹이나 dfs, 트리 탐색등등에서 굉장히 여러분야에서 사용되는 기본적인 개념이다.