재귀

개요

재귀적 구조란 자기자신을 정의할 때 자신보다 1차 낮은 부분집합을 사용하고, 또한 그 부분집합은 그보다 차수가 낮은 부분집합을 사용해서 정의하는 과정을 반복하는 구조다. 이러한 구조를 일반적으로 재귀라한다. 재귀를 사용하면 복잡한 알고리즘을 명료하게 기술할 수 있기 때문에 현대 프로그래밍 기법에서 중요한 제어구조의 하나로 여겨진다. 재귀는 프로그램 내에서 일반적으로 다음과 같은 구조를 이룬다. 재귀 호출에는 반드시 탈출 지점이 있어야 한다. 만약 탈출지점이 없다면 재귀 호출은 영원히 계속되고, 컴퓨터의 저장공간 한계로 인하여 스택 오버플로우가 발생하게 된다.

재귀함수 {
     탈출조건을 충족 => 함수를 리턴한다.  
      ..... (중간 수행 부분)
     재귀호출 => 스스로를 호출한다
}

이떄 재귀함수는 프로그램내에서 스택을 이용하여 호출되게 된다. 먼저 호출된 함수는 프로그램의 수행 순서를 저장하는 부분에 (Stack Register) 차례로 저장되며, 리턴을 하게되면 스택에서 pop하여 수행하게 된다.

예시 1) 팩토리얼의 구현

long factorial(int n) {
    if(n == 1)
        return n
    return factorial(n-1)*n
}

예시 2) 피보나치 수열

long fib(long n) {
    if(n == 1 || n == 2)
        return 1

    return fib(n-1) + fib(n-2)
}

예시 3) 유클리드 호제법 (나머지 함수를 써서 한번에 할 수도 있지만, 좀더 이해를 쉽게 하기 위해)
<syntaxhighlight>
int euclid(int m, int n) {
    if(m>n)
        return euclid(m-n,n)
    if(m < n)
        return euclid(n-m.m)
    //한방에 euclid(n,m%n) 이렇게 해도 된다. 
    if(m==n)
        return m
}

특징

1. 알고리즘을 구현할 떄 재귀적 표현이 적합한 경우 비 재귀적으로 바꾸려면 복잡함을 감수해야 한다.
2. 재귀적인 데이터 구조 (트리, 그래프)를 다루는 경우 재귀를 사용하면 훨씬 편하게 할 수 있다.
3. 재귀를 이용한 팩토리얼에서 나타낸 바와 같이 함수의 끝부분에 단 한 번만 재귀 호출을 하는 것을 tail recursion 이라고 한다. 이 경우에는 간단하게 반복을 이용한 비재귀적 방법으로도 구현할 수 있고 더 효과적이다.
4. 재귀적 방식은 비재귀적 방법에 비해 실행시간이 약간 더 걸린다. (스택에 넣고 빼는 시간으로 인해서)