[Data Structures] 챕터2. 재귀(Recursion)

재귀호출

---

재귀호출은 종료조건이 반드시 필요하다

 

가시화 도구

https://pythontutor.com/cpp.html#mode=edit 

- 가시화 도구에서는 함수 실행이 끝나면 stack 메모리 자체가 사라진다. 실제로는 우리가 프로그램을 실행시킬때 (OS가 프로세스를 만들어줄 때) 여유있는 크기의 stack 메모리를 미리 주고 편하게 사용하는 방식이다.

- 함수 호출이 끝날 때 stack 메모리의 일부를 OS에게 반환하는 일은 없다(새 스택마다 메모리를 요청/반납하면 느려짐)

- heap 메모리 공간은 매번 OS에게 요청하고 반납해야 합니다.

 

실행 위치에 따라 결과가 달라진다

void RecurFunc(int count)
{
    if (count == 0) // <- 종료 조건
        return;

    cout << count << endl;
    RecurFunc(count - 1); // 출력 후 호출
}

 

void RecurFunc(int count)
{
    if (count == 0) // <- 종료 조건
        return;

    RecurFunc(count - 1); // 출력 전 호출
    cout << count << endl;
}

 

재귀로 합 구하기

---

int RecurSum(int* arr, int n)
{
    if (n == 0)
        return 0;

    return RecurSum(arr, n - 1) + arr[n - 1];
    /*        ( 1 + 2 + ... 8 + 9  + 10)
            = ( 1 + 2 + ... 8 + 9) + 10
            = ((1 + 2 + ... 8) + 9) + 10
    */
}

나머지값 + 마지막 값으로 분리하여 계산함이 핵심이다.

 

공간복잡도 분석

재귀호출을 사용하여 총합을 구한 함수는 공간복잡도 O(n)이다.

함수를 호출할 때 스택에 저장되는 데이터를 Frame이라 한다.

 

Frame은 아래 데이터를 저장한다

- 함수를 실행할 때 필요한 데이터

- 실행이 끝난 후 돌아가야할 위치 데이터

 

재귀 합 분석

---

시간복잡도

- 아래 함수를 참고하면 반복문은 2n+3, 재귀호출은 2n+2번 실행된다.

- 반복문, 재귀호출 모두 O(n)이다.

- 재귀호출이 더 느리다(재귀호출은 함수 호출에 필요한 추가적인 작업을 실행한다)

int step_count; // 전역 변수 카운트

int Sum(int* arr, int n)
{
    int sum = 0;

    step_count++; // 위의 sum = 0

    for (int i = 0; i < n; i++)
    {
        step_count++; // for
        sum += arr[i];
        step_count++; // assignment
    }

    step_count++; // for last time of for
    step_count++; // for return

    return sum;
}

int RecurSum(int* arr, int n)
{
    step_count++; // 아래에 있는 if, true 가 아니라도 비교는 하기 때문에 여기에서 증가

    if (n <= 0)
    {
        step_count++; // return
        return 0;
    }
    else
    {
        step_count++; // return
        return (RecurSum(arr, n - 1) + arr[n - 1]);
    }
}

 

피보나치 수열

---

내 풀이(공간복잡도가 높다)

int Fibonacci(int n)
{
    int fn = 0;

    int* arr = new int[n];
    arr[0] = 0;
    arr[1] = 1;

    for (int i = 2; i < n; ++i)
        arr[i] = arr[i - 1] + arr[i - 2];

    fn = arr[n-1] + arr[n-2];

    return fn;
}

 

정답(공간복잡도가 낮다)

int Fibonacci(int n)
{
    int fn = 0;
    int pre1 = 0;
    int pre2 = 1;

    for (int i = 2; i <= n; ++i)
    {
        fn = pre1 + pre2;
        
        // Shift
        pre1 = pre2;
        pre2 = fn;
    }

    return fn;
}

 

재귀 이진 탐색

---

재귀호출로도 이진탐색을 구현할 수 있다.

int RecurBinarySearch(int* arr, int left, int right, int x) // n 대신에 left, right
{
    if (left <= right)
    {
        int middle = (left + right) / 2;

        if (x < arr[middle])
            return RecurBinarySearch(arr, left, middle-1, x);
        else if (arr[middle] < x)
            return RecurBinarySearch(arr, middle+1, right, x);
        else
            return middle;
    }

    return -1;
}

 

순열 문제(재귀호출 활용)

---

1. 재귀호출 될 때마다 앞 글자가 정해진다 (재귀호출)

2. 정해지는 글자는 모든 경우의 수를 고려한다 (반복문)

3. Right index는 재귀호출이 반복되어도 고정된다.

4. 재귀호출에서 빠져나올 때(트리에서 올라올 때) 원상복구하여 다음 경우의 수를 준비한다.

5. 종료조건은 한 글자가 남았을 때이다. Left == Right로 확인할 수 있다.

void RecurPermutations(char* arr, int left, int right)
{
    if (left == right)
    {
        for (int i = 0; i <= right; i++)
            cout << arr[i] << " ";
        cout << endl;
    }
    else
    {
        for (int i = left; i<=right; ++i)
        {
            swap(arr[left], arr[i]);

            RecurPermutations(arr, left + 1, right);

            swap(arr[left], arr[i]);
        }
    }
}

int main()
{
    /*  abc 3 글자의 순열 (Permutations)

        a b c
        a c b
        b a c
        b c a
        c b a
        c a b
    */

    // Permutations
    char arr[] = "abcd";

    //RecurPermutations(arr, 0, 2);
    //cout << endl;

    RecurPermutations(arr, 0, 3);
    cout << endl;

    return 0;
}

https://leetcode.com/problems/permutations/

https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/