[필기,면접]재귀호출과 메모리 영역

본 책에서 재귀호출에 대한 내용이 있었다. 재귀호출은 코딩테스트에서도 기본문제로 자주 나오는 편이고 필자는 필기시험에서 피보나치수를 재귀호출을 사용하여 손코딩을 하는 문제를 많이 봤었다. 혹시 모르는 사람을 위해 간단한 Persuade code를 보자면

#include<iostream>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
 
using namespace std;
 
int fibonacci(int n) {
    if (n==0) {
        printf("0");
        return 0;
    } else if (n==1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}
 

위와 같다. 위 코드는 첫항이 0일때의 코드이고 1이라면 n==0 일때 return 1로 바꿔주면 된다.

우선 책의 내용을 간단하게 정리하면, 

재귀호출(DFS)  -이진 탐색이 기본-

- 함수를 호출하는데 따르는 오버헤드가 크기때문에 반복보다 비효율적이다, 함수 파라미터는 지역변수로 스텍에 할당되므로 비효율적

기본 코드

void dfs(int a) {
    visit[a] = 1;
    printf("%d ", a);
    for (int i = 1; i <= n; i++)
        if (arr[a][i] == 1 && arr[i][a] == 1 && visit[i] == 0)
            dfs(i);
}

위와 같이 나타낼수 있다. 인접행렬을 통해 서로 연결되어 있는것끼리 탐색한다. 혹시 관련 문제를 보고싶다면 아래 문제링크가 있다.

DFS : https://www.acmicpc.net/problem/1260

재귀호출의 또 다른 기본인 이진 탐색이 있다. 중요한 내용이다. 시간복잡도는 O(logn)이며 원소가 정렬된 상태여야한다. 원리는 설명하지 않고 Persuade code만 확인해보자.

int bin(int ar[], int chk, int n) {
    int l=0, r=n-1, m;
    while (l <= r) {
        m = (l + r) / 2;
        if (ar[m] > chk) r = m - 1;
        else if (ar[m] < chk) l = m + 1;
        else return 1;
    }
    return 0;
}

m이라는 Middle값을 기준으로 좌, 우를 좁혀가면서 탐색하는 방법이다. 손코딩문제로 자주 출제되니 중요하다.

위 코드는 재귀호출이 아닌 while반복문을 통해 작성한 코드이다. 

-재귀 호출-

int bin(int *arr, int s, int e, int k) {
    if (s > e) return -1;
    int mid = (s + e) / 2;
    if (mid == k) return mid;
    else if (arr[mid] > k) return bin(arr, s, mid - 1, k);
    else return bin(arr, mid + 1, e, k);
}

재귀호출의 기본내용은 여기까지이고 '오버헤드가 크기때문에 반복보다 비효율적' 이라는 말을 이해해보자.

이 말을 이해하기 위해선 먼저 메모리영역에 관해 알고 있어야 한다. 메모리영역 또한 시험에 자주 출제되므로 알고 넘어가자

메모리 영역

        

   

Code 영역 : 코드 자체를 구성하는 메모리 영역, 프로그램 명령이 위치하는 곳

 

Data 영역 : 전역,정적,구조체 등의 변수들이 저장된다. 함수 내부의 Static변수는 프로그램이 실행 될 때 공간만 할당되고 함수실행시 초기화됨

Heap 영역 : 동적 메모리를 할당하고자 할 떄 위치하는 메모리 영역 (C : malloc, C++ : new)

Stack 영역 : 지역, 매개 변수들이 사용되었다 사라지는 데이터를 저장하는 영역

*오버플로우 : 스택과 힙에 할당된 메모리 영역보다 더 큰 메모리영역이 필요해서 발생

*오버헤드 : 프로그램 실행흐름에서 나타나는 현상, 실행중, 동떨어진 위치의 코드를 실행할 때, 추가적으로 드는 시간,메모리,자원 등