[C] 재귀함수(Recursive/리쿼시브)의 개념과 공부하는 이유

재귀란 무엇인가?

컴퓨터 과학에 있어서 재귀(再歸, Recursion)는 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻하며, 이를 프로그래밍에 적용한 재귀 호출(Recursive call)의 형태로 많이 사용된다. 또 사진이나 그림 등에서 재귀의 형태를 사용하는 경우도 있다. (위키백과)

 

위키백과에서 가져온 재귀의 컴퓨터 과학 측면에서의 정의이다. 쉽게 말해서, "재귀적으로 정의했다" 라는 말은 자기 자신을 정의할 때 자기 자신을 이용했다는 것이다.

 

가령 5! (5 팩토리얼)을 정의할 때도,

5! = 5 * 4! 라고 나타낼 수 있으므로 이를 일반화하면

n! = n * (n - 1)!

라고 나타낼 수 있게 된다.

이 등식에서 팩토리얼을 정의하는데 있어서 팩토리얼을 사용했다는 것은, 재귀적 정의를 활용했다고 할 수 있는 것이다.

재귀적 정의의 조건

어떤 개념을 재귀적으로 정의하기 위해서는 두 가지 Step이 필요하다.

 

  - Recursive step : 자기 자신을 호출하는 step

     ex) n! = n * (n - 1)!

  - Termination step : 재귀를 벗어나기 위한 step

     ex) 0! = 1

 

여기서 Termination step, 즉 종료 조건이 매우 중요한데, 위 예시에서 Recursive step만 존재할 경우

5! = 5 * 4!

4! = 4 * 3!

3! = 3 * 2!

2! = 2 * 1!

1! = 1 * 0!

0! = 0 * (-1)!

(-1)! = (-1) * (-2)!

이렇게 끝없는 재귀의 굴래에서 빠져나오지 못하게 된다.

그래서 Termination step을 0! = 1 로 정의해 줌으로써 팩토리얼의 재귀적 정의가 비로소 완성되는 것이다.

예시

#include<stdio.h>

int factorial(int k);

int main()
{
    int result = factorial(5);
    printf("result: %d\n", result);
    
    return 0;
}

int factorial(int k)
{
    if(k == 0)
        return 1;
    else
        return k * factorial(k - 1);
}

factorial 함수에 5가 들어갔을 때,

 

    Depth1: <factorial(5)> 종료조건이 충족되지 않으므로 return 5 * factorial(4); / 값이 반환될 때까지 대기

    Depth2: <factorial(4)> 종료조건이 충족되지 않으므로 return 4 * factorial(3); / 값이 반환될 때까지 대기</factorial(4)>

    Depth3: <factorial(3)> 종료조건이 충족되지 않으므로 return 3 * factorial(2); / 값이 반환될 때까지 대기</factorial(3)>

    Depth4: <factorial(2)> 종료조건이 충족되지 않으므로 return 2 * factorial(1); / 값이 반환될 때까지 대기</factorial(2)>

    Depth5: <factorial(1)> 종료조건이 충족되지 않으므로 return 1 * factorial(0); / 값이 반환될 때까지 대기</factorial(1)>

    Depth6: <factorial(0)> 종료조건이 충족되었으므로     return 1;</factorial(0)>

 

    Depth5: return 1 * 1;

    Depth4: return 2 * (1 * 1);

    Depth3: return 3 * (2 * (1 * 1));

    Depth2: return 4 * (3 * (2 * (1 * 1)));

    Depth1: return 5 * (4 * (3 * (2 * (1 * 1))));

 

    result = 5 * 4 * 3 * 2 * 1 * 1 = 120

재귀함수를 왜 공부할까?

어떤 구조를 재귀적으로 표현하면 매우 간결한 느낌을 줄 수 있지만 프로그램 실행 과정도 그럴까?

오히려 재귀적으로 구현한 로직보다 일반적인 반복문을 사용하여 구현하는 로직이 더 빠른 경우가 많다.

재귀가 결코 효율적인 알고리즘이 아니라는 뜻이다.

 

조금 전에 살펴보았던 factorial 함수의 실행 흐름만 잘 생각해봐도 알 수 있다.

함수는 호출될 때마다, 그 안에서 정의되는 매개변수와 다른 변수들의 메모리를 할당하게 된다.

 

그런데 함수 안에서 자기 자신을 호출하게 되면, 그 안의 변수들을 다른 메모리 공간에 할당하고,

그 안에서 또 자기 자신을 호출하면, 또 그 안의 변수들을 메모리 공간에 할당하고 ... ...

결국 재귀 알고리즘에서 많은 Depth를 수행하게 되면 그만큼의 메모리가 누적된다는 것이다.

하지만, 그럼에도 불구하고 재귀 알고리즘을 사용하는 이유는, 사람이 이해하기 쉽고 명쾌한 표현이 가능하기 때문이다.

 

[C언어_14] 재귀함수의 개념과 공부하는 이유 (tistory.com)