함수와 재귀함수

• 자료구조

1. 스택 (함수의 호출방식과 닮았다.)

2. 큐

 

함수가 사용하는 메모리 공간을 스택 메모리 공간이라고 한다.

 

• 스택

 

위와 같이 함수를 호출하면 결과가 되돌아온다.

같은 함수를 연달아 호출하면 이전 메모리가 삭제된 시점 이후 연산해 리턴하고, 메모리에서 삭제 한다.

int iData = Add(100, 200); -> 300을 리턴해 변수에 할당 한 뒤 함수 스택 메모리에서 삭제
int iData = Add(300, 400); -> 700을 리턴해 변수에 할당 한 뒤 함수 스택 메모리에서 삭제

 

※ 코드와 메모리 영역은 같은 개념이 아니다!

코드는 명령어의 집합으로, 일종의 작업 명령서와 같다. (EX. 땅을 파서 건물 2채를 지어라.)

메모리 영역은 명령 수행에 맞춰 동작하고 있는 곳으로 일종의 땅 덩어리다. (코드 수행 후 건물 2채 지음)

또한 함수는 이러한 코드, 즉 명령어의 집합체이다.

 

// 함수 예시 : 팩토리얼 구현하기
int Factorial (int _iNum)
{
	int iValue = 1;
    for (int j = 0; j < _iNum - 1; ++j)
    {
    	iValue *= (j+2);
    }
    return iValue;
}

int main()
{
	int iValue = Factorial(4);
    iValue = Factorial(10);
    
    return 0;
}

 

특정 기능을 함수화하면 코드가 간결해지고 재사용성이 증가하며, 더 복잡한 기능을 만들 때 수월하고 쉽게 구현할 수 있다.

 

• 함수 사용 시 주의사항
  
  0. 함수 이름의 의미
  변수와 동일하게  함수도 그에 대한 내용이 존재하고 메모리를 써서 내용을 표현한다.
  이미 배웠듯이 메모리가 존재한다면 그에 대한 위치도 무조건 필요하다.
  이때 이름이란 그 메모리의 위치를 의미한다. (즉, 이름 == 주소값 == 위치이다.)
  
  함수가 실행됐다면 모든건 램에서 내 프로그램이 실행된 프로세스 영역에 존재해야 한다.
  이때 램이란 결국 n바이트의 1열의 연속이므로 주소를 표현한다는 건 램에서 N번째 바이트(위치)를 의미한다.
  
  
  1. 함수는 다른 함수 내부에서는 선언할 수 없다. (클래스의 경우 inner class라는 개념이 있으나 함수에선 존재하지 않는다.)
  
  2. 함수는 return 값이라는 것이 무조건 존재한다.
  리턴 값은 임시 변수로 메모리 어딘가에 저장되었다가 사용된다.
  
  따라서 아래와 같이 sizeof()를 사용할 수 있다.
  
  
   sizeof(Plus(20, 30)); // 이미 4바이트가 임시변수를 통해 할당되었으므로 sizeof를 사용할 수 있다.
  
   bool bResult;
   bResult = Plus(20, 30); // 1바이트가 아니라 int를 리턴받았으므로 4바이트 자료형을 1바이트로 저장했을 뿐이다.
  
  
  
  이처럼 함수를 할당하고 해제할 때, return 값을 임시 변수로 저장할 때 메모리가 사용되기 때문에,
  함수를 많이 만들 수록 프로그램은 느려지게 된다.
  
  리턴 값이 없는 경우 함수는 종료되지 않고 대기한다. (void의 경우 return; 키워드만 있으면 된다
  
  3. 함수를 실행하는데 필요한 메모리 비용은 언제나 매개변수 크기 + a 이다.
  즉, 함수에 매개변수가 int 하나만 있다면 이 함수를 실행할 때 필요한 메모리는 4바이트 + a이다.

 

• 재귀함수

재귀함수 : 함수 안에서 자기 자신을 호출(※)하는 상황.

※ 호출스택 : 각 함수에 대한 로컬 내용을 볼 수 있게 해줌. 내부 메모리 확인으로 디버깅에 도움이 된다.

 

지역 변수 : 함수 안에 선언된 변수들. 메인함수가 호출될 때 쓰는 메모리 영역(스택 메모리영역)

 

자기 함수 안에서 자기를  호출한다 : 메모리에 함수 호출 시 현재 쌓인 함수 위로 다음 함수가 쌓임.

이때 자시 자신을 또 호출하면 그 위로 새로운 함수 스택이 또 쌓인다.

이렇게 스택에 쌓인 메모리는 실행이 끝나면 각각 종료되면서 없어진다.

종료시 호출스택에서 사용된 값을 다음 스택에 전달하기 위헤서, 리턴 값은 CPU에 내장된 레지스터 메모리에 잠시 저장되었다가 메모리 영역에서 해당 스택이 사라지고나면 다음 스택에 레지스터에 저장된 리턴 값을 꺼내와서 집어넣는다.

이런 과정을 반복하다보면 언젠가는 main 함수로 돌아가게 된다.

하지만, 이 경우 함수가 제대로 종료될 수 있도록 자기 자신을 다시 호출하는 작업을 해당 함수에서 호출해선 안된다.

반드시 탈출 조건이 있어야 한다. 탈출 조건이 없으면 스택이 계속해서 쌓이면서 스택 메모리 초과로 Stack Overflow 에러가 발생한다.

# 잘못된 예
int Factorial(int _iNum)
{
	int iValue = 1;
    for (int j = 0; i < _iNum - 1; ++j)
    {
    	iValue *= (j+2);
    }
    Factorial(10); // 탈출 조건이 없으므로 잘못된 예시이다.
    return iValue;
}

 

• 재귀 함수는 어떨때 쓰나?

프로그래밍 숙련시 재귀 함수는 가독성과 구현의 용이에서 장점을 가진다.

하나의 함수에서 여러개의 변수를 쓰지 않고도 스택 메모리 안에 남아 있는 데이터를 재활용하여 지역변수처럼 사용할 수 있기 때문이다. 하지만 단점 역시 존재한다. 함수 호출, 해제에 대한 비용이 있으므로 성능 면에서 실수 여지가 있으므로 유의해서 사용해야 한다.

 또한 재귀 함수는 계층 구조를 표현할 때 유용하게 사용할 수 있다. 따라서 계층 구조로 데이터를 나타내는 트리 구조 구현시에도 사용된다.

 

// 재귀함수로 팩토리얼 구현하기
int Factorial_Re(int _iNum)
{
	if(1 == _iNum) // 계속 반복되다가 1이 될 때 함수를 빠져나온다.
    {
    	return 1;
    }
    
    return _iNum * Factorial_Re(_iNum-1);
}

int Main()
{
    iValue = Factorial_Re(10);
    return 0;
}

// 피보나치 수열 -> 재귀함수 없이 구현하기
int Fibonacci(int _iNum)
{
	if(1 == _iNum || 2 == _iNum)
    {
    	return 1;
    }
    
    int iPrev1 = 1;
    int iPrev2 = 1l
    int iValue = 0;
    
    for(int i=0; i < _iNum-2; ++i)
    {
   		iValue = iPrev + iPrev2;
        iPrev1 = iPrev2;
        iPrev2 = iValue;
    }
    
    return iValue;

}

// 피보나치 수열을 재귀함수로 구현하기
int Fibonacci_Re(int _iNum)
{
    if(1 == _iNum || 2 == _iNum)
    {
    	return 1;
    }
    
    return Fibonacci_Re(_iNum-1) + Fibonacci_Re(_iNum-2);
}

 

재귀 함수를 사용하여 더욱 코드가 간결해졌음을 확인할 수 있다.