재귀

함수가 return 되기전에 그 함수를 다시 재 호출 하는 것을 재귀 라고 한다.

 

재귀는 나중에 DFS (깊이우선탐색) 알고리즘과 DP 등과 연결되어 있어서 개념을 잘 숙지해야하며 활용할 수 있어야 한다.

 

가장 대표적으로인 재귀함수와

 

팩토리얼

 

을 함수의 재귀 호출로 값을 구해보는 시간을 가졌다.

 

void recall(int n)

{

    if (n == 1)

    {

        printf("%d end", n);

        return;

    }

    printf("%d\n", n);

    return recall(n - 1);

}

기본적인 재귀 함수

 

int factorial(int n)

{

    if (n == 0)

    {

        return 1;

    }

    else

    {

        return n * factorial(n - 1);

    }

}

재귀함수는 재귀의 탈출조건인 base case가 매우 중요하다

 

base case가 지정되지 않으면 함수가 무한으로 호출되기 때문이다.

 

factorial 함수의 basecase는 n == 0 일때 이다.

 

int main()

{

    recall(3);

    printf("\n");

    printf("%d", factorial(4));

    return 0;

}

구현한 재귀 함수의 실행결과를 짐작하여 보자