[C] 재귀 함수 Recursion function

최근 코딩면접을 준비하고 있는데, 어떤 인사 담당자님께서 재귀함수에 대해서는 알지만, 재귀함수을 계속 쓰게되면, 프로그램이 죽는데, 왜 죽고 

이를 방지하기 위해 어떤 방법을 써야하는지에 대해서 모른다고 뽑고싶어도 사람을 뽑을 수 없다고, 한탄하시는 글을 읽고 찔려서 ㅎㅎ... 

공부하게 되었습니다.

피보나치 수열

피보나치 수열의 정의는 다음과 같습니다.

이를 프로그래밍에서 구현하게되면, 다음과 같은 재귀함수로 구현할 수가 있습니다.

Fibonacci - Recursion

#include <stdio.h>
 
int fibonacci_recursion(int n){
    if(n < 2){
        return n;
    }
    else{
        return fibonacci_recursion(n-1) + fibonacci_recursion(n-2);
    }
}
 
int main(void){
 
    printf("fibonacci_recursion 40 : %d\n", fibonacci_recursion(40));
 
    return 0;
}

제 컴퓨터에서는 해당 재귀함수에 50이라는 숫자만 넣어도, 프로그램이 돌다가 죽습니다.

프로그램이 죽는 이유에 대해서 간단하게 이야기하면, 재귀함수의 규모는 호출이 많이질 수록 기하급수적으로 커지는데 비해, 프로그램 실행을 저장하는 

Call Stack의 크기는 한정되있기 때문입니다.

피보나치 수열을 구하는 재귀함수는 다음과 같이 실행됩니다.

따라서 i값이 증가하면 증가할수록 재귀함수의 규모는 기하급수적으로 커지게 됩니다. 

프로그램 코드 정보를 저장하는 스택 자료구조(Call Stack)이 있는데, 해당 자료구조는 다음과 같습니다.

이런 형태로 프로그램 실행 순서를 메모리에 LIFO(Last In First out) 형태로 쌓게 되는데, 이 쌓게되는 양이 한계가 있습니다.

따라서 재귀함수에서 호출하는 함수의 주소는 해당 Call Stack에 쌓이는데, 해당 Call Stack의 양은 한계가 있고, 재귀함수 규모가 커져서 해당 Stack의 크기를

넘어가게 되면, Stack Overflow가 일어나게 됩니다. 

그래서 프로그램은 Stack Overflow가 일어나게되면, 프로그램을 죽이게끔 설계가 되어있습니다. 안그러면, 다른 프로그램이랑 충돌이 일어나 치명적인 상황을

만들 수 있기 때문입니다.