재귀함수,꼬리재귀함수,스택 오버 플로우(Stack overflow)

#include<iostream>

void Func(int _Value)
{
   std::cout << _Value << std::endl;
   
   Func(++_Value);
}

int main()
{
   Func(0);
}

재귀 함수란 위의 코드와 같이 함수안에서 자기를 또 호출하는 방식이다.

위의 코드를 실행하면 0부터 계속 ++되면서 출력하다가

프로그램이 터져버린다.실행 원리를 생각해보면

처음에 Func(0)이 스택에 올라가서 실행되고 그 안에서 Func(0) 함수가 종료되기전에

Func(1)이 실행된다.함수는 함수가 종료될때 메모리에서 사라진다.

그치만 위의 실행순서를 보면 Func(0)이 종료되기 전에 Func(1)이 스택에 올라오고

실행된다.이게 계속 반복되면서 메모리에는 Func(0),(1),(2)... 이렇게 계속 쌓이는거다.

그러면서 Stack 영역이 꽉 차고 프로그램이 터져버린다.(개념적으로 생각하면 Heap영역까지 간다고 볼수있다.)

이런 경우를 스택 오버 플로우(Stack overflow)라고 한다

#include<iostream>

void Func(int _Value)
{
   std::cout << _Value << std::endl;
   
   if (10 < _Value)
   {
      return;
   }
   
   Func(++_Value);
}

그렇기 때문에 위의 코드처럼 코드를 빠져나올 수 있는 조건이 있어야한다.

그러면 Func(0) 이 함수가 실행되고 10개의 정리되지 않은 메모리가

한번에 정리되게 되는거다.이런 문제점이 있기 때문에 꼬리재귀라는 문법이 있다.

#include<iostream>

void Func(int _Value)
{
   std::cout << _Value << std::endl;
   
   if (10 < _Value)
   {
      return;
   }
   
   return Func(++_Value);
}

위의 코드와 같이 return으로 반환해서 자기를 호출하는 방식이다.

꼬리 재귀로 할경우 컴파일러가 반복문 형식으로 고쳐준다.

그래서 스택에 메모리가 쌓이지 않는다.그렇지만 언제나 바꿔주는것이 아니고

함수가 너무 복잡하면 바꿔주지 않는 경우도 있다.

재귀함수를 꼭 써야하는 경우라면 꼬리재귀로 사용하는 것이 좋다.