재귀 (1) - 개요

1. 재귀함수란?

재귀함수란 자기 자신을 호출하는 함수를 의미한다. 아래 예시(팩토리얼)을 보자. 이렇게 재귀호출을 이용하면 코드를 깔끔하고 읽기 좋게 짤 수 있게 된다. 팩토리얼의 경우 N!과 같이 표기하며 자연수 N이 주어지면 1부터 N까지의 수열을 모두 곱하는 함수를 의미한다.

 

int factorial(int n){
	if(n == 0) 
        return 1;
    else 
        return n * factorial(n-1); 
        // recurssion call 
}

 

2. 잘못된 재귀호출

그러나 모든 재귀호출이 좋은 것은 아니다. 재귀호출은 굉장히 조심히 사용해야하는 테크닉인데 아래의 잘못된 예시들을 보면 무엇이 잘못되었는지 알게 된다. 첫번째 예시의 rose() 함수는 끊임없이 자기 자신의 함수를 호출하고 있다. 이렇게 계속해서 함수를 호출하게 되면 stack 메모리가 가득차서 stack overflow 문제에 빠질 수 있다. 그렇다면 자기자신만 호출하지 않으면 될까? 두번째 예시는 자기자신을 호출을 호출하지 않지만 두 함수가 서로가 서로를 호출하여 결국 stack overflow에 빠지게 된다. 또한 이러한 함수들에서는 아무런 정보를 얻을 수 없다. (영희의 집이 철수의 집 주변인데, 철수의 집에 대한 정보도 영희의 집 주변이라는 정보만 있으면 결국엔 어떠한 정보도 얻을 수 없다)

 

예시 1 : 장미는 장미이다.

void rose(){
    rose();
}
    

 

예시2 : 철수의 집은 영희의 집 주변이다. 영희의 집은 철수의 집 주변이다.

void young(){
    chul();
}

void chul(){
    young();
}

 

3. 올바른 재귀호출 : Devide & Conquer

그렇다면 어떻게 해야 재귀호출을 올바르게 사용할 수 있을까? 정답은 devide & conquer 전략을 구현하는데에 활용하는 것이다. devide & conquer는 말 그대로 커다란 문제를 작은 문제로 쪼개고, 가장 작은 문제의 해답으로 부터 다시 커다란 문제를 풀어나가는 전략으로 실제로 사용되던 전쟁 전략이였지만, 이를 컴퓨터 프로그래밍 영역으로 재해석한 경우에 해당한다. devide & conquer 전략의 사용법은 다음과 같다.

 

• 재귀호출을 끝내는 종료조건(기저)이 있어야한다. 
• 문제의 크기가 종료조건(기저)을 향해 가야한다.
• 기저(더 이상 쪼갤 수 없는 상황)의 결과를 조립한다.

 

위에서 봤던 팩토리얼 함수를 다시 살펴보자. 만약 5!가 주어지면 5 x 4 x 3 x 2 x 1과 같이 계산할 수 있다. 이 떄 우리는 5!을 5 x 4!와 같이도 쓸 수 있다. 4! = 4 x 3!이고 3! = 3 x 2!이고 2! = 2 x 1!이고 1! = 1 x 0!인데 0! = 1이다(이는 수학적 정의이다) 때문에 0!을 알면 어떠한 자연수의 팩토리얼도 구할 수 있게 되는 것다. 이 때 더 이상 쪼갤 수 없는 0!를 바로 기저(Basis)라고 하며, 재귀함수의 종료조건은 바로 기저가 되는 조건이다. 

 

int factorial(int n){
    if(n == 0) 
        return 1;
        // end point (basis)
    
    else 
        return n * factorial(n-1); 
        // n is going to basis
}

 

팩토리얼 함수에는 파라미터 n이 있다. 올바른 재귀호출을 위해서는 이 n이 기저에 가깝게 변해가야한다. 때문에 재귀호출 부분에서 factorial(n)을 그대로 호출하지 않고 factorial(n-1)을 호출하였다. n은 자연수이기 때문에 1씩 점점 빼다보면 반드시 기저(0)에 도달한다. 마지막으로 factorial(0)이 리턴되면 함수를 호출하면서 쌓여왔던 스택들이 반환되면서 결과값들이 조합되고 최종 결과값을 찾게 된다.

 

다음 포스트부터는 재귀호출과 Devide & Conquer로 구현할 수 있는 여러가지 애플리케이션 구현체들(Fibonacci, Hanoi, Flood Fill, Fractal Tree, RFF)을 업로드할 예정이다. 재귀함수를 이용하는 애플리케이션은 무궁무진 하지만 이 블로그에서는 대표적으로 이재규님의 C++로 배우는 알고리즘에서 소개된 애플리케이션만 다룰 예정이다.

 

4. Refernce