예제로 알아보는 재귀 함수

오늘은 재귀 함수에 대해서 알아보려고 합니다.

재귀는 사전적 의미로 원래 자리로 되돌아온다는 뜻을 갖고 있습니다.

재귀 함수는 함수 안에서 자신을 호출하는 함수를 뜻합니다.

 

 

 

예제 1

#include "stdio.h"
 
void recall_func(void);
 
int main(void)
{
    recall_func();
 
    return 0;
}
 
void recall_func(void)
{
    printf("function call\r\n");
    recall_func();
}
 

예제 1 출력 결과

무수히 많은 출력을 합니다. 실제로 recall_func()이라는 함수에서만 출력이 되는 것처럼 보이지만 계속해서 새로운 함수를 실행하는 것과 같습니다. 함수 호출을 하게 되면 메모리를 사용하기 때문에 일정 시간 경과 후 Stack overflow가 발생이 되어 프로그램이 자동으로 종료가 됩니다. 이는 할당된 Stack 메모리를 모두 사용하였기 때문입니다. 따라서 종료를 위한 조건식을 넣어야 합니다.

 

recall_func()이라는 함수에서만 반복이 되는 것처럼 보이지 않고 새로운 함수에서 실행되는 것과 같이 보이도록 예제를 한 번 더 보겠습니다.

 

 

 

예제 2

#include<stdio.h> 
 
void recall_func(int val);
 
int main(void)
{
    recall_func(2);
    
    return 0;
}
void recall_func(int val)
{
    printf("val = %d, &val = %d\n", val, &val);
 
    if (val == 0)
    {
        return;
    }
    recall_func(val - 1);
    printf("val = %d, &val = %d\n", val, &val);
}

조건식이 1개 추가가 되고 출력이 한 개가 더 늘었을 뿐 예제 1번과 크게 달라 보이지 않습니다. 그러면 출력 결과를 한번 보겠습니다.

 

 

예제 2 출력 결과

만약 recall_func() 함수에서만 반복이 되었다면 분명 0에서 끝났겠지만 0에서 끝나지 않았습니다. 즉, 함수를 호출할 때마다 새로운 함수를 호출하는 것과 같습니다.

 

출력 값의 주소를 보면 해당 숫자와 주소가 반복이 되고 있습니다.

 

 

예제 2 풀이

int main(void)
{
    recall_func(2);
    
    return 0;
}

1. 최초 main에서 recall_func(2)를 호출합니다.

 

 

void recall_func(int val)
{
    printf("val = %d, &val = %d\n", val, &val);

    if (val == 0)
    {
        return;
    }
    recall_func(val - 1);

2. 최초 값(val = 2)을 출력하고 새로운 복사본 recall_func(1)을 실행합니다.

 

3. 새로운 복사본 recall_func(0)을 실행하고 값은 0이 되어 return이 됩니다.

 

4. 여기서 이전의 복사본 recall_func(2), recall_func(1)은 끝나지 않았습니다. 따라서 재귀 호출 함수를 최초로 호출한 main문이 아닌 이전 recall_func(1)로 돌아갑니다.

 

    printf("val = %d, &val = %d\n", val, &val);
}

5. 초기 recall_func(2), recall_func(1) 순서대로 실행됐으므로 recall_func(1), recall_func(2) 순서대로 출력이 됩니다.

 

// 출력
val = 2, &val = 19922252
val = 1, &val = 19922036
val = 0, &val = 19921820
val = 1, &val = 19922036
val = 2, &val = 19922252

return전과 후의 출력 val = 2 일 때 val =1 일 때 주소 값이 같은 것을 볼 수 있습니다. 같은 복사가 된 함수가 실행이 된 것입니다. 하나의 함수에서 반복이 되는 것으로 보이지만 새로운 함수를 실행하는 것과 동일한 것입니다.

 

 

 

 

2020/02/26 - [프로그래밍/C++] - 프로그래머스 - 완주하지 못한 선수, sort algorithm 정리

2020/01/05 - [프로그래밍/C] - 이중 연결 리스트(Double linked list), 이중 원형 연결 리스트 예제

2019/12/22 - [프로그래밍/C] - 프로그래머스 2016년, 날짜에 따른 요일 구하기

2020/08/17 - [프로그래밍/C#] - C# 시리얼 통신 아스키 외 값 읽기

2020/08/27 - [프로그래밍/C#] - C# USB 통신, LibUsbDotNet