[C++ 때려 잡기] C++ 기초강의 2-4 재귀함수

2018/08/24 - [교육 노트/C++ 기초강의] - [C++ 때려 잡기] C++ 기초강의 2-1 함수의 선언과 정의

2018/08/25 - [교육 노트/C++ 기초강의] - [C++ 때려 잡기] C++ 기초강의 2-2 함수 오버로딩

2018/08/25 - [교육 노트/C++ 기초강의] - [C++ 때려 잡기] C++ 기초강의 2-3 call by value / call by reference

우리가 만든 함수를 여러번 실행시키기 위해서는

그냥 여러번 쓰면되지만

우리는 이미 반복문을 배웠기때문에 반복문을 통하여 함수를 반복하여 실행시킬수가 있다.

for문과 while문으로 함수를 반복하여 사용가능한데

함수의 반복의 경우 특수한 방법이 하나 더 존재한다.

바로 재귀를 이용하는것이다.

1. 재귀

재귀(recursive) 자기 자신에게 되돌리는 것을 의미
재귀 함수 자기 자신을 호출하는 함수

재귀는 자기 자신에게 되돌리는 것이며 재귀함수는 함수내에서 자기 자신을 호출하여 반복되는 함수를 의미한다.

간단한 예제를 살펴보자

#include <iostream>

using namespace std;

void countNum(int num)

{

  if (num == 1)

  {

    cout << "Num : " << num << endl;

    return;

  }

  else

  {

    cout << "Num : " << num << endl;

    countNum(num - 1);

  }

}

int main()

{

  countNum(5);

  return 0;

}

countNum 함수는 num 이 1일때를 재외하고 파라미터로 받은 num의 -1을 다시 파라미터로 주는 함수를 호출한다.

따라서 num : 5를 출력하고 num: 4를 출력하는 함수를 함수 내에서 호출하는것이다.

이것을 반복하여 더이상 자기 자신을 호출하지 않는 num==1이 될때까지 자기 자신을 호출하는것이다.

해당 함수를 다른 반복문에서는 구현해 보자면

다음과 같다.

재귀함수가 더 길고 복잡해 보이는거처럼 보이지만

재귀함수는

일반적인 수학의 점화식을 그대로 표현가능한 능력을 가지고있어

프랙탈, 분할반복등에서 엄청난 효율을 보여준다.

재귀를 이해하기위하여

1. 팩토리얼을 for, while, 재귀로 구현해보자

2. 피보나치 수열을 for, while, 재귀로 구현해보자

3. 최대 공약수, 최소공배수를 구하는 프로그램을 for, while, 재귀로 구현해보자

또한 2번째 기초강의가 끝났다

사실상 포인터를 제외하고 객체지향에 넘어가지 전에 C++의 문법의 기초는 다 끝난것이다

지금까지 배운 내용을 통하여 다음실습을 해보자.

4. 해당 숫자가 소수(prime number)인지 판별하는 프로그램을 제작해보자

5. 행맨 게임을 제작하라 (프로그램 참조), 행맨게임에서 문제는 미리정해놓은 하나의 단어로만 하도록 한다.

6. 기존에 만든 가위바위보 게임을 화면출력 함수, 게임 결과 함수 등으로 나누어 만들어라