Chankyu Lee

ㅎㅇㅎㅇ

본 내용은 어소트락 무료 강의 <C/C++ 무료강의>을 기반으로 공부한 내용을 정리한 것이다. 틀린 내용이 있을 수도 있음.

재귀 함수 (1)

재귀함수란? : 함수 안에서 자기 자신을 호출하는 녀석.

(중요) 호출 스택 ? => 코드 내 문제점을 추적 시 유리하다. 잘 활용하자.

호출 스택 : 현재 호출되고 있는 함수들의 메모리 상황을 보여준다. 즉 현재 스택 메모리 영역 내에서 어느 함수 지역(로컬)을 보고 있는지를 알 수 있다.

호출 스택이 여러개일때 그에 맞는 로컬에서의 값들을 확인한다.

함수 내에서 자기 자신을 호출하는 재귀 함수는 호출만 하고 사라지지 않아 계속해서 쌓이게 된다. 때문에 반드시 탈출조건이 필요하며 탈출이 되지 않아 정해진 메모리 영역을 넘치게 된다면 스택 오버 플로우(Stack Over Flow) 에러가 발생한다.

재귀 함수의 장단점

  • 장점
    • 코드 가독성이 좋다.
    • 구현에 용이하다.
  • 단점
    • 스택오버플로우 에러 발생 가능성이 있다.
    • 성능 저하가 발생할 수 있다.

재귀 함수 (2) - 재귀함수를 이용해 코드의 가독성을 높인다.

Factorial 함수를 재귀함수로

Factorial 함수를 재귀함수로 표현

int Factorial_Re(int _iNum)     //  Recursive : 재귀 -> Re는 이름상 붙인 것 int _iNum = 함수 호출시 받을 값
{
    if (1 == _iNum)             //  1! = 1 이므로 if문을 이용해 고정시킴
    {
        return 1;
    }
    
    return _iNum * Factorial_Re(_iNum - 1);     // 자기 자신 함수를 호출
}

재귀함수로 피보나치 수열 함수 만들기

피보나치 수열 : 1, 2, 3, 5, 8, 13, …. 처럼 앞과 뒤 숫자의 합이 다음 순서가 되는 수열

피보나치 수열 함수

int Fibonacci(int _iNum)
{
    if (1 == _iNum || 2 == _iNum)       
    {
        return 1;                           // if 구문을 통해 첫번째, 두번째 숫자 고정
    }
    int iPrev1 = 1;                         // 기본적으로 앞 숫자 + 뒷 숫자 = 다음 숫자 이므로 초기값 설정
    int iPrev2 = 1;
    int iValue = 0;                         // 결과값이 0부터 시작하게

    for (int i = 0; i < _iNum - 2 ; ++i)    // for문을 이용해 다음 숫자 계산
    {
        iValue = iPrev1 + iPrev2;           // 결과값 = 다음 숫자 = 앞 숫자 + 뒷 숫자
        iPrev1 = iPrev2;                    // 다음 계산에서 뒷 숫자가 앞 숫자가 되어야 함
        iPrev2 = iValue;                    // 그 뒷 숫자는 계산 결과값과 같다.
    }
    return iValue;                          // 결과값 리턴
}

피보나치 수열 함수를 재귀함수로

int Fibonacci_Re(int _iNum)
{
    if (1 == _iNum || 2 == _iNum)           // if구문 동일
    {
        return 1;
    }

    return Fibonacci_Re(_iNum - 1) + Fibonacci_Re(_iNum - 2);
    // 4번째 피보나치 수를 구할 때, 3번째(4-1) + 2번째(4-2) 숫자의 합을 구하므로 다음과 같다.  
}

피보나치 재귀함수의 한계?

  • 함수 호출이 굉장히 느리다고 한다. 후에 “꼬리재귀(Tail Recursive)”를 통해 이를 해결한다.
  • 재귀함수는 “계층 구조”를 표현할 때 효율이 대박이다. 후에 “Tree” 구조때 매우 핵심이 된다.

참고