[C/C++] 재귀호출

재귀호출
재귀호출은 함수가 내부에서 자기 자신을 호출을 하는 것을 이야기합니다. 자칫 치명적인 오류를 범할 수도 있고, 꼭 재귀호출을 사용하지 않더라도 분명 많은 방법으로 동일한 결과를 얻을 수 있습니다. 그러나, 어떤 알고리즘을 구현하다 보면 재귀호출은 분명 매력적인 방법입니다. 그 중에서 오늘은 팩토리얼(Factorial), 피보나치(Fibonacci)와 하노이(Hanoi)탑 문제를 재귀호출로 구현하는 것을 보여드리겠습니다.

본 자료는 국립 창원대학교 메카트로닉스 공학부 학생을 대상으로 한 컴퓨터 언어 응용 수업 자료입니다. 본 자료는 수업의 교재인 (핵심요약판) C++로 시작하는 객체지향 프로그래밍 (Y. Daniel Liang 저, 권기형 / 김응성 공역) 의 내용을 재구성한 것으로 수업보조 자료 이외의 목적이 없음을 알립니다.

팩토리얼 Factorial

고등학교 수학시간에 배운 팩토리얼계산이 기억나시죠? 6! = 6*5*4*3*2*1 .. 이렇게 계산했었는데요. 이걸 구현하는 거야 간단히 for문정도 사용해주면 될겁니다만... 재귀호출로 생각을 해보죠. 재귀호출을 사용할 때는 생각을 재귀적(^^?)으로 하면 쉽습니다.

원래 0!은 1이니까. 팩토리얼 함수를 위와 같이 자기자신을 이용, 즉 재귀적으로 정의를 내려주면 됩니다. 좀 더 자세히 생각해보면

 
바로 위와 같지요. 3!을 구하라고 하면, 3*2!이라고 생각하는거지요. 다시 2!은 2*1!이 되는거고, 또 1!은 1*0!이고, 원래 정의에서 0!은 1이라고 해 두었으니 끝나는 거죠. 

<코드1>

#include <iostream>
using namespace std;

// Return the factorial for a specified index
int factorial(int);

int main()
{
  // Prompt the user to enter an integer
  cout << "Please enter a non-negative integer: ";
  int n;
  cin >> n;

  // Display factorial
  cout << "Factorial of " << n << " is " << factorial(n);

  system("pause");
  return EXIT_SUCCESS;
}

// Return the factorial for a specified index
int factorial(int n)
{
  if (n == 0) // Base case
    return 1;
  else
    return n * factorial(n - 1); // Recursive call
}

  

피보나치 수열

한 영화에서 유명해진 피보나치 수열. 고등학교때는 아마 토끼의 번식에 관해 예제가 다뤄지는 걸로 알고 있는데요.

위와 같은 피보나치 수열을 생각해보죠. 앞선 두개를 더해서 현재것을 만들어내는 것이 본래 정의입니다. 첫번째는 0, 두번째는 1이라고 하고나서 보면, 역시 재귀적으로 표현할 수 있네요. 

 
<코드2> 

#include <iostream>
using namespace std;
// The function for finding the Fibonacci number
int fib(int);

int main()
{
  // Prompt the user to enter an integer
  cout <<  "Enter an index for the Fibonacci number: ";
  int index;
  cin >> index;

  // Display factorial
  cout << "Fibonacci number at index " << index << " is "
    << fib(index) << endl;

  system("pause");
  return EXIT_SUCCESS;
}

// The function for finding the Fibonacci number
int fib(int index)
{
  if (index == 0) // Base case
    return 0;
  else if (index == 1) // Base case
    return 1;
  else // Reduction and recursive calls
    return fib(index - 1) + fib(index - 2);
}

하노이 탑

하노이 탑 문제입니다. 크기순으로 정렬해 있는 탑을 반대편으로 옮기는 것인데요. 한번에 하나만 들 수 있고, 절대 작은것 위에 큰것이 옮겨질 수 없죠. 이것도 재귀적으로 생각할 수 있습니다. 쉽게 생각하면 위 그림에서 보면 A의 제일 큰, 그러니까 제일 밑에 있는 원판이 C로 옮겨지는 거죠. 즉, 현재 제일 큰 원판이 목표지점으로.. 라고 생각해 두면 됩니다. 

 
<코드3>

#include <IOSTREAM>
using namespace std; 
/* The function for finding the solution to move n disks
    from fromTower to toTower with auxTower */
void moveDisks(int n, char fromTower,
    char toTower, char auxTower)
{
  if (n == 1) // Stopping condition
    cout << "Move disk " << n << " from " << fromTower << " to " << toTower << endl;
  else
  {
    moveDisks(n - 1, fromTower, auxTower, toTower);
    cout << "Move disk " << n << " from " << fromTower << " to " << toTower << endl;
    moveDisks(n - 1, auxTower, toTower, fromTower);
  }
}

int main()
{
  // Read number of disks, n
  cout << "Enter number of disks: ";
  int n;
  cin >> n;

  // Find the solution recursively
  cout << "The moves are: " << endl;
  moveDisks(n, 'A', 'B', 'C');

  system("pause");
  return EXIT_SUCCESS;
}

  

참고자료 [2009] 08.pdf