본문으로 바로가기

[C/C++] 재귀호출

category Theory/Lecture 2009.11.15 14:43

재귀호출
재귀호출은 함수가 내부에서 자기 자신을 호출을 하는 것을 이야기합니다. 자칫 치명적인 오류를 범할 수도 있고, 꼭 재귀호출을 사용하지 않더라도 분명 많은 방법으로 동일한 결과를 얻을 수 있습니다. 그러나, 어떤 알고리즘을 구현하다 보면 재귀호출은 분명 매력적인 방법입니다. 그 중에서 오늘은 팩토리얼(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




댓글을 달아 주세요

  1. BlogIcon 테리우스원 2009.11.16 16:26 신고

    너무 어려워요 머리가 아픈 것 같아요 ㅎㅎㅎ
    즐거운 시간으로 승리하시길

    사랑합니댜 행복하세요!!

  2. 감사합니다. 2010.02.04 22:37 신고

    잘 읽고 갑니다.

  3. 재귀.. 2010.04.28 12:10 신고

    재귀에 대한 것을 발표 하기 위해 자료를 찾다가 우연히 방문하였습니다
    저는 재귀에 대해 발표 자료를 준비하면서 피보나치 수열만 생각했습니다
    재귀적이란게 자기 자신을 호출한다는 뜻인데
    하이노의 탑은 봐도 잘 이해가 안되네요
    혹시 자세히 알수있을까 해서 글남깁니다

    • BlogIcon PinkWink 2010.04.29 06:00 신고

      종이와 펜을 가지고 아마 직접 프로그램을 따라 가보셔야 할겁니다.^^ 위에 있는 하노이탑코드는 재귀용법을 사용하면서도, 함수의 입력이 바뀌고 있습니다. A B C로 입력을 호출한 다음 A C B로 입력을 바꾸고 있지요. 블럭 넘버에 유의해서 보셔야합니다. 하노이 탑에 대해서는 간단히 설명할게 아니라서 다시 보강 포스팅을 할 계획입니다.^^

  4. BlogIcon yemundang 2010.06.26 21:05 신고

    오.. 이 얼마만에 보는 코드인지...
    옛추억 새록새록 되새기면서.. 가끔 심심하면 글보고 공부해야겠습니다.
    학교다닐 땐 재미 없었는데, 지금 보니까 반갑네요? ㅎㅎㅎ

  5. siddang 2010.08.11 04:36 신고

    c++ 에 대해 정리가 잘 되어있어서 많은 도움 얻고 갑니다. 혹시 CLASS 에 대해서 정리해두신 것은 없는지요? 요새 공부 중인데 혼자 공부하기에는 이해가 잘 안되는 듯 해서요..

    • BlogIcon PinkWink 2010.08.11 11:07 신고

      수업을 CLASS까지 하질 않아서.. 관련 문서가 없네요. 가능하시면, 위키디피아의 CLASS문서를 확인하시면 설명을 보실수있습니다.^^

  6. HHU 2011.12.08 12:32 신고

    재귀호출에 대해서 배우는데 와 감사합니다 ~
    굽신굽신굽신굽신

  7. C쁘루 2015.10.23 12:12 신고

    넘 유용해요 감사합니당