재귀함수는 언제, 어떻게 사용하죠?(on c)

본 포스트는 C언어를 중심으로 작성되었습니다.다만 설명을 위하여 python 코드를 일시적으로 넣었음을 알려드립니다.

 

재귀함수는 언제, 어떻게 사용하죠?

 

재귀 ? 재귀란 본디의 곳으로 돌아오는 것이라는 사전적 의미를 내포하고 있습니다. 컴퓨터 공학에서는 어떤 의미를 갖고있을까요?

 

컴퓨터 과학에 있어서 재귀는 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻하며, 이를 프로그래밍에 적용한 재귀 호출의 형태로 많이 사용된다. _위키백과 참조

 

라고 합니다. 자 이렇게 설명하면, 알아듣기 까다롭죠! 또 예시를 들어야 이해가 한번에 파바박 될겁니다 

 

이해를 돌기위한 코드를 준비했습니다! 보통 재귀함수는 그림, 사진 분야 분석에서 많이 활용되며, 특히 알고리즘 문제에서는 단골 손님이죠! 저 또한 가볍지 않게 생각하는 존재입니다-_-;

 

 

 

 

예전에 간단하게 만들었던 시에르픈스키 삼각형 그리기 코드입니다. 함수내에 선언된 자기 자신을 계속해서 호출해주며 프로그래머가 원했던 값을 출력하는 것이라고 생각하면 편합니다. 

 

하지만 이런 의문을 품을 수 있습니다. 계속해서 호출하다면 혹시 메모리릭? 혹은 무한루프에 돌지 않을까? 맞습니다. 정확하게는 제어를 해주지 않았을 때 그런 상황이 발생한다는 것이죠.

 

그렇기 때문에 함수 내에 첫번째 코드는 제어문을 삽입 후 사용하는것이 바람직합니다.

 

그렇다면 간단한 예제 2개를 보고 이번 포스팅을 마치도록 하겠습니다!

1. 팩토리얼 함수

 

대표적인 재귀호출 함수 중 하나라 할 수 있는 팩토리얼 함수입니다.  자연수 n에 대한 팩토리얼 함수는 1부터 n까지의 모든 자연수를 곱하는 함수입니다. 즉 n! = n x (n-1)!을 구하기 위해선 (n-1)!값을 알아야 한다는 의미와 맞물립니다.

 

간단하게 코드로 보여드리면,

 

 

#include <stdio.h>
 
#include <string.h>
 
int facto(int n){//재귀함수를 사용한 예
 
    if (n<=1)
 
        return 1;
 
    else
 
        return (n*facto(n-1));//n이 1보다 작거나 같을때 1을 반환할때 까지 자신을 호출
 
}
 
int facto(int n){ // 반복문을 활용한 예
 
    int i,f =1;
 
    if(n<=1)
 
        return 1;
 
    else{
 
        for(i = n; i>=0; i++)
 
            f = f*i;
 
        return f;
 
    }
 
}
 
 
 
 
 
 
 

위 코드를 볼때 재귀함수를 사용한 예와 반복문을 사용한 예를 보았는데 어떤가요? 재귀함수를 사용한 예가 훨씬 더 보기 깔끔하고 코드의 명료성이 확보됩니다.

 

그렇다고해서 재귀함수가 우월하게 반복문보다 좋다라는것은 절대로 아닙니다. 유지보수, 간결성 측면에서 좋지만, 메모리문제를 야기하기 쉽고, 스택의 메모리가 한정되어 있어 코드 상의 프로그램이 강제적으로 종료될 확률이 있습니다.

 

2. 하노이의 탑

앞서 설명드렸을 때 재귀함수는 메모리문제를 야기시킬 수 있다고 언급했습니다. 그럼에도 불구하고 왜 재귀함수를 사용하는지 알아보겠습니다. 사실 위와 같은 팩토리얼 문제에서는 재귀함수를 굳이 사용해야할 필요를 느끼지 못합니다. 그러나 아주 복잡한 재귀 문제는 재귀함수를 사용해야 해결할 수 있다는 점을 명심하시기 바랍니다.

 

하노이의 탑 아시죠? 어렸을 때 어머님들이 우리 아이가 영재가 아닌가 하고 해본다는 ㅋㅋ.. 물론 저도 해보았지만, 네 지극히 평범합니다. 룰은 아시리라 믿지만, 모르시는 분을 위해 간략히 룰에 대해 기술하겠습니다.

 

1. A,B,C라는 봉이 세개 있습니다. 각 봉은 시작, 중간, 끝이라 두고 시작점에 있는 원반들을 끝의 지점으로 옮기는것이 목표입니다.

 

2. 원반은 세개가 있다고 가정합니다. 원반은 소 , 중 , 대 의 크기로 크기가 큰 순서가 맨 아래에 위치 하고 있는 구조를 지닙니다.

 

3. 크기가 큰 원반은 절대로 크기가 자신보다 작은 원반 상위로 존재할 수 없습니다.

 

4. 또한 각 원반은 옮길때 단 한차례만 옮길 수 있으며, 여러개를 한번에 옮길 수 없습니다.

 

흠 설명이 되었을 까요?

 

 

그냥 그림을 만들어 드리는게 낫겠죠? ㅎㅎ 보시다 시피 맨 끝 봉으로 옮깁니다. 각 원반의 갯수별로 최소 이동 수가 존재합니다.  최소 이동수를 지키며 맨 끝 봉으로 옮기는 방법은 어떤게 있을지 생각해보시기 바랍니다.

 

아주 간단한 규칙만 따르시면 사실 풀 수 있습니다.

 

 

 

" 시작봉의 원반이 홀수 일때 원반을 끝봉으로 옮기고, 시작봉의 원반이 짝수일때는 중간봉으로 옮겨준다 " 이 원칙만 머릿속에 기억하시고 문제푸시면됩니다.

 

 

 

 

문제를 풀자면,

 

 

 

초기상태의 원반에서 시작봉에 있는 가장 작은 원반을 끝봉으로 옮긴 후 중간 원반을 중간봉으로 옮기고, 끝 봉에 있는 가장 작은 원반을 중간원반 위로 위치시킵니다. 그런 후 가장 큰 원반을 끝봉으로 옮기고 중간 봉에 위치한 가장 작은 원반은 다시 시작 봉으로 옮긴 후에, 중간 원반은 끝봉으로 옮깁니다. 그런 후 마지막으로 가장 작은 원반을 끝봉에 위치시켜 주며 마무리 지으시면 되겠습니다 (최소 이동횟수 : 7)

 

 

 

그렇다면 세 단계로 나누어 생각해볼까요?

 

1 단계 : 시작봉에 있는 원반 1~n-1을 끝 봉을 이용해 중간 봉으로 옮깁니다.

2 단계 : 시작봉에 있는 마지막 원반을 끝 봉으로 옮깁니다.

3 단계 : 중간 작업봉에 있는 원반1 ~ n-1원반을 시작봉을 이용해 끝봉으로 옮깁니다.

 

 

#include <stdio.h>
 
void hanoi (int n, int start, int middle, int end);
 
int main(){
 
    hanoi(3, 'A','B','C');
 
    return 0;
 
}
 
void hanoi (int n, int start, int middle, int end)
 
{
 
    if (n==1)
 
        printf("%c에서 원반 %d를 %c로 옮겼습니다.\n",start, n, end);
 
    else{
 
        hanoi(n-1, start, end, middle);
 
        printf("%c에서 원반 %d를 %c로 옮겼습니다.\n",start, n ,end);
 
        hanoi(n-1, middle, start, end);
 
    }
 
}
 
 
 
 
 
 
 
 
 

출력 결과 : 위와 같이 출력됨을 알 수 있습니다.

 

재귀 함수는 한번 봐서 이해하기 쉽진 않고, 계속해서 여러번 봐야 아 이렇구나 느낍니다. 더 이해가 안갈때는 그림을 그리면서 이해를 돕는 것또한 많은 도움이 됩니다.

 

이해안가시는 부분 댓글 달아주세요! 피드백 환영입니다!

 

읽어주셔서 감사합니다.