[C] 재귀 함수 (Resurcive Function)

재귀 함수(Resurcive Function)

함수 내에서 자기 자신을 호출하는 함수를 의미한다

#include <stdio.h>

void recur(int count);

int main(void)
{
    recur(3);

    return 0;
}

void recur(int count)
{
    printf("%d\n", count);

    if (1 == count)
    {
        return;
    }

    recur(count - 1);
}

 

 

재귀 함수의 핵심

재귀 함수 속 return의 위치와
재귀 함수 속  함수가 호출되는 위치가 매우 중요하다

 

다시 말해,

재귀 함수 속

return의 위아래로 어떤 코드를 작성하느냐,

함수 호출 위 아래로 어떤 코드를 작성하느냐에 따라 결과물이 달라진다

 

#include <stdio.h>

void recur(int count);

int main(void)
{
    recur(3);

    return 0;
}

void recur(int count)
{
    printf("%d\n", count);

    // return의 위
    if (1 == count)// return 조건 및 내부
    {
        return;
    }
    // return의 아래

    // 재귀 함수 호출 위
    recur(count - 1);
    // 재귀 함수 호출 아래
    
}

 

 

재귀 함수의 장단점

 

 

Tree Recursion

트리 형태의 재귀함수 호출 방식이다

기초적인 재귀함수와 다르게 2차원적인 호출 구조를 가진다

반복문으로는 구현이 불가능하고,

알고리즘에서 이러한 형태 및 재귀 함수가 많이 사용된다

#include <stdio.h>

size_t fibonacci(size_t num);
size_t fibonacci_rec(size_t num);

int main(void)
{
    printf("%zu\n", fibonacci(6));
    printf("%zu\n", fibonacci_rec(6));

    return 0;
}

size_t fibonacci(size_t num)
{
    size_t fib = 1;
    size_t prev = 1;

    if (num <= 2) {
        return 1;
    }

    for (size_t i = 3; i <= num; ++i) {
        size_t temp = fib;
        fib += prev;
        prev = temp;
    }

    return fib;
}

size_t fibonacci_rec(size_t num)
{
    if (num == 1 || num == 2)
    {
        return 1;
    }

    return fibonacci_rec(num-1) + fibonacci_rec(num-2);
}

 

 

꼬리 호출(Tail Call)

재귀함수가 가독성도 좋고, 재사용성도 뛰어나지만

함수 호출이기 때문에 너무 빈번한 호출은 오버헤드를 발생한다

이를 없애기 위해서는,

Caller 함수의 블럭 스코프 마지막에서 Callee 함수를 호출해서

Caller의 스택프레임을 유지할 필요가 없게 되며

이를 꼬리 호출이라고 한다

다시 말해, Caller 함수의 블럭 스코프 마지막에 Callee 함수를 호출하는 경우를 의미한다

 

꼬리 호출 최적화(Tail-Call Optimization)

꼬리 호출의 경우에 컴파일러가 스택프레임을 따로 만들지 않는 최적화를 진행한다

 

꼬리 재귀(Tail Recursion)

Caller 함수와 Callee 함수가 같은 꼬리 호출을 하는 경우를 꼬리 재귀라고 한다

이 경우에도 꼬리 호출 최적화가 진행된다

꼬리 재귀는 사실상 가독성이 너무 떨어지기 때문에

면접 대비 용도로 개념정도만 기억하고, 일반재귀를 권장한다

// 꼬리 재귀를 사용하지 않은 경우
#include <stdio.h>

long long int factorial(int n);

int main(void)
{
    printf("%lld", factorial(5));

    return 0;
}

long long int factorial(int n)
{
    if (n <= 1) 
    {
        return 1;
    }

    return n * factorial(n - 1);
}

 

// 꼬리 재귀를 사용한 경우
#include <stdio.h>

using namespace std;

int factorial(int n);
int calculateFactorial(int n, int res);

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

    return 0;
}

int factorial(int n)
{
    return calculateFactorial(n, 1);
}

int calculateFactorial(int n, int res)
{
    if (n <= 1) {
        return res;
    }

    return calculateFactorial(n - 1, n * res);
}