Skip to content

60. 함수 재귀호출

1. 키워드

  • 재귀호출(Recursive Call)


2. 함수에서 재귀호출 사용하기

  • 함수 안에서 함수 자기자신을 호출하는 방식을 재귀호출이라고 한다.
  • 재귀호출은 일반적인 상황에서는 잘 사용하지 않지만 알고리즘을 구현할 때 매우 유용하다.


3. 재귀호출 사용하기

  • 먼저 간단한 재귀호출 함수를 만들어보자.


#include <stdio.h>

void hello()
{
    printf("Hello, world!\n");

    hello(); // hello 함수 안에서 hello 함수 호출
}

int main()
{
    hello(); // hello 함수 최초 호출

    return 0;
}

// Hello, world!
// Hello, world!
// Hello, world!
// ...(생략)


  • hello 함수 안에서 다시 hello 함수를 호출하고 있다.
  • 소스 코드를 컴파일하여 실행해 보면 "Hello, world!" 문자열이 계속 출력되다가 프로그램이 종료된다.
  • 왜냐하면 hello 함수가 자기자신을 계속 호출하다가 스택이 넘쳐서 스택 오버플로우 에러가 발생하기 때문이다.


001


  • 재귀호출을 사용하려면 반드시 다음과 같이 종료 조건을 만들어줘야 한다.


#include <stdio.h>

void hello(int count)
{
    if (count == 0) // 종료 조건을 만듦. count가 0이면 다시 hello 함수를 호출하지 않고 끝냄
        return;

    printf("Hello, world! %d\n", count);

    hello(--count); // count를 감소시켜서 다시 hello에 넣음
}

int main()
{
    hello(5); // hello 함수 호출

    return 0;
}

// Hello, world! 5
// Hello, world! 4
// Hello, world! 3
// Hello, world! 2
// Hello, world! 1


  • 먼저 hello 함수의 반복 횟수를 계산하기 위해 매개변수 count를 지정한다.
  • 그리고 count가 0이라면 hello 함수를 호출하지 않고 끝낸다.
  • 만약 0이 아니라면 "Hello, world!"를 출력하고 count의 값을 1씩 감소시켜서 hello 함수를 호출할 때 넣어준다.


void hello(int count)
{
    if (count == 0) // 종료 조건을 만듦. count가 0이면 다시 hello 함수를 호출하지 않고 끝냄
        return;

    printf("Hello, world! %d\n", count);

    hello(--count); // count를 감소시켜서 다시 hello에 넣음
}


  • main 함수에서는 hello 함수를 반복할 횟수를 넣어서 호출해 준다.
  • 이렇게 하면 hello 함수가 재귀호출을 할 때마다 count에 들어있는 값이 1씩 감소하고, 0이 되면 재귀호출을 끝낸다.


hello(5); // hello 함수 호출


002


4. 재귀호출로 팩토리얼 구하기

  • 이번에는 재귀호출을 사용하여 팩토리얼(Factorial)을 구현해 보자.
  • 팩토리얼은 1부터 n까지 숫자를 차례대로 곱한 값이며 !(느낌표) 기호로 표기한다.
  • 예를 들어 5!은 5 * 4 * 3 * 2 * 1이며 결과는 120이다.


#include <stdio.h>

int factorial(int n)
{
    if (n == 1)   // n이 1일 때
        return 1; // 1을 반환하고 재귀호출을 끝냄

    return n * factorial(n - 1); // n과 factorial 함수에 n - 1을 넣어서 반환된 값을 곱함
}

int main()
{
    printf("%d\n", factorial(5));

    return 0;
}

// 120


  • 먼저 factorial 함수를 만들 때 매개변수와 반환값을 int 타입으로 지정해 준다.
  • 여기서 팩토리얼은 1부터 n까지의 곱을 구하는 문제인데 여기서는 n부터 역순으로 1씩 감소하면서 재귀호출을 하고 n이 1이 되었을 때 재귀호출을 중단한다.


int factorial(int n)
{
    if (n == 1)   // n이 1일 때
        return 1; // 1을 반환하고 재귀호출을 끝냄


  • factorial 함수의 핵심은 반환값 부분이다.
  • 계산 결과가 즉시 구해지는 것이 아니라 재귀호출로 n - 1을 계속 전달하다가 n이 1일 때 비로소 1을 반환하면서 n과 곱하고 다시 결괏값을 반환한다.
  • 그런 다음 n과 반환된 결괏값을 곱하여 다시 반환하는 과정을 반복한다.


return n * factorial(n - 1); // n과 factorial 함수에 n - 1을 넣어서 반환된 값을 곱함


  • factorial(5)를 호출해서 n이 1이 될 때까지 재귀호출을 하면 다음과 같은 모양이 된다.


003


  • 이제 if (n == 1)을 만나서 factorial 함수가 1을 반환한다.
  • 그런 다음 1과 2를 곱해서 2를 반환하고, 3과 2를 곱해서 6을 반환하고, 4와 6을 곱해서 24를 반환하고, 5와 24를 곱해서 120을 반환하게 된다.


004


  • factorial 함수의 계산 과정을 그림 하나로 표현하면 다음과 같이 된다.


005

References