[C언어] 재귀함수! 반복문 없이 반복되는 함수 만들기

C언어 뿐만 아니라 모든 언어에서 기본적으로 사용하는 구문들은 전부 알아보았습니다. 변수, 상수, 반복문, 조건문, 그리고 마지막으로 함수까지 말이죠. 이것만으로도 여러가지 응용을 해서 프로그래밍을 만들 수 있습니다.

 

 

오늘은 함수의 응용으로 재귀함수를 알아볼 예정입니다. 재귀함수는 반복문 없이 함수의 반복을 만들어 주는 구문입니다.

---

재귀함수: 함수에서 함수를 부르다!

재귀함수는 사용자 정의 함수를 만들고 이 함수에서 다시 사용자 정의함수를 부르는 함수를 말합니다. 사용자 정의 함수에 대해서는 지난 포스팅에서 다뤄봤습니다.

 

2020/09/28 - [쿤즈 Dev/C] - [C언어] 함수(Function) (2) 사용자 정의 함수의 사용법

[C언어] 함수(Function) (2) 사용자 정의 함수의 사용법

 

어떤 값을 반복해서 구해야 하고 이 함수의 결과값을 이용해서 다시 함수를 호출하여 반복해야 하는 경우 반복문(for, while, do while)을 사용하지 않고 함수를 사용하는 방법입니다. 이러한 함수가 재귀함수입니다.

 

위 Flow 를 보시면 main() 함수에서 recursion() 이라는 함수를 호출(Call) 하였습니다. 호출된 함수는 내부의 로직을 실행하는데 다시 중간에 자기 자신과 동일한 이름의 recursion() 함수를 다시 호출하게 됩니다. 이와 같은 방법으로 계속해서 자기 자신의 함수를 부르는 형태입니다.

 

여기서 주의할 사항은 내부에서 조건문을 사용하여 함수의 종결을 지어줘야합니다. 그렇지 않으면 무한루프와 같이 끝없이 함수가 반복되게 되기 때문입니다.

 

그럼 소스코드를 통해서 다시 알아보도록 하겠습니다.

---

소스코드1 recursive.c

#include <stdio.h>

int factorial(int);

int main(int argc, const char* argv[]) {
    int result;
    int number;

    printf("Factorial 을 계산할 수를 입력하세요 : ");
    scanf_s("%d", &number);

    result = factorial(number);
    printf("%d ! = %d\n", number, result);
    return 0;
}

int factorial(int num) {
    if (num > 1) {
        return num * factorial(num - 1);
    }

    return 1;
}

결과1

Factorial 을 계산할 수를 입력하세요 : 5
5 ! = 120

소스코드1은 factorial 을 구하는 프로그래밍입니다. factorial은 어떤 수보다 작거나 같은 모든 양의 정수의 곱을 뜻하는 용어입니다. factorial 은 느낌표(!)로 표시합니다. 예를들어서 3! = 3 * 2 * 1 의 결과로 6이 됩니다. 이러한 수를 for 문이나 while 문으로 만들어 볼 수 있지만 이번 포스팅에서는 재귀함수를 사용해보도록 하겠습니다.

 

for문과 while 문은 아래 포스팅에서 확인하시면 됩니다.

2020/08/25 - [쿤즈 Dev/C] - [C언어] 반복문의 시작! - for 구문

2020/09/14 - [쿤즈 Dev/C] - [C언어] 반복문 두 번째 - while 구문

2020/09/15 - [쿤즈 Dev/C] - [C언어] 반복문 세 번째 - do while

 

먼저 가장 상단에 factorial() 함수의 원형을 선언하였습니다. 선언은 반드시 main() 함수 위에서 선언해 줘야 합니다. 그리고 정의는 main() 함수 아래에 두었습니다.

 

Factorial 을 구하기 위해서 사용자의 키보드로부터 값을 받는 함수인 scanf_s() 를 사용했습니다. scanf() 를 사용해도 되지만 이 경우에는 문제가 발생하기 때문에 대체 함수를 사용해서 값을 저장합니다.

 

[C언어] 표준입력 표준출력 사용하기 (첫 프로그래밍 시작!)

여기서 중요한 부분은 factorial() 함수입니다. 이 함수는 parameter 로 정수형 값을 1개를 받아옵니다. 그렇게 받은 값은 최초 1 보다 큰 값인지 비교해야 합니다. 만약 1보다 작은 값이 들어올경우엔 더이상 함수를 반복하지 않도록 막아야 하기 때문입니다.

 

 

1보다 큰 값이 들어올경우 변수 num 에 저장된 값과 그보다 작은 값을 곱해줍니다. 만약 3을 인자로 받아서 num에 저장한 경우 3 * factorial(2) 가 되는 것입니다. 그럼 다시 factorial(2) 는 함수로 돌아와 2 * factorial(1) 이 됩니다. 이 결과를 차례대로 return 하게 되면 3 * 2 * 1 이 되며 다시 처음으로 돌아올경우 return 되는 값은 6이 되는 것입니다.

---

재귀함수의 장단점

재귀함수는 결과적으로만 보면 반복문(for, while, do while)과 같은 결과를 낼 수 있습니다. 하지만 재귀함수보다 반복문을 사용하면 훨씬 더 빠르고 효과적인 프로그래밍을 할 수 있습니다.

 

 

다만 자료구조적인 면에서 재귀함수는 리스트 또는 이진 트리에서 효과적으로 사용이 되며, 스택과 같은 자료구조에서도 널리 사용하는 방법입니다. 자료구조에서 자세히 다뤄볼 내용일 수 있지만 기본적인 C언어의 구조이기 때문에 알고 넘어가시면 좋습니다.

---

오늘은 재귀함수에 대해서 알아보았습니다. 기본적인 구조는 사용자 정의 함수를 프로그래머가 만들면서 재귀함수를 만드는 작업을 진행합니다. 다만 주의해야 할 사항은 무한반복에 빠지지 않게 반드시 내부 조건문이 필요합니다. 어떤 구조에서는 재귀함수가 효과적일 때가 있으니 사용법을 익혀 두시는 것도 좋을것 같습니다.