[C] 재귀 함수(1) , Factorial 함수

[C] 재귀 함수(1) , Factorial 함수

---

 

목차

1. 스택 메모리 영역이란?

2. 재귀 함수란?

3. Factorial 기능을 구현하고 싶다.

3.1. Factorial 기능의 그냥 코드 구현

3.2. Factorial 기능의 함수 구현

3.3. Factorial 기능의 재귀 함수 구현

4. 피보나치 기능

4.1. 피보나치 수열의 함수 구현 (재귀 함수 (2))

4.2. 피보나치 수열의 재귀 함수 구현 (재귀 함수 (2))

---

1. 스택 메모리 영역이란?

C, C++ 언어를 공부하고 있는 사람은 기본적으로 main 함수를 사용하고 있을 것이다.

 

함수가 사용하는 메모리 영역 : 스택 메모리 영역

 

Stack(스택)  : 선입 후출, 후입 선출 (나중에 들어온 애가 먼저 나간다. 예: 쌓인 그릇, 엘리베이터)

엘리베이터에 사람들이 우르르 탔을 경우 삐 무게 초과 소리가 나면 제일 마지막에 탄 사람이 내리는 것과 유사하다.

 

Queue(큐)  : 선입 선출, 후입 후출 (먼저 들어온 애가 먼저 나간다. 예: 급식소)

급식소에 우리가 달려가는 이유는 먼저 간 사람이 먼저 먹는다는 것을 알기 때문이다. 이와 유사하다.

 

 

스택은 나중에 들어온 애가 먼저 나가서, 함수의 방식과 유사해서 함수 메모리 영역을 스택 메모리 영역이라고 한다.

---

2. 재귀 함수란?

재귀 함수의 개념을 이해하기 위해서는 먼저 스택에 대한 이해가 있어야 한다.

함수의 안에서 또 함수를 호출하는 것은 스택처럼 하나하나 쌓여가고 제일 마지막 함수가 끝나면 그다음 마지막 함수부터 차례로 수행이 끝나며 맨 처음 함수로 돌아온다. 

 

A(B(C(D()))) 가 있으면 A함수를 수행하다 내부의 B함수에 들어가게 되고 B함수를 진행하다 내부의 C함수에 들어가게 되고 C함수를 진행하다 내부의 D 함수를 수행한다. D함수 수행이 끝나면 차례로 C->B->A순으로 나와 코드를 다 돌고 끝난다.

 

스택이 한계치에 달하면 스택오버플로우가 발생한다. 어딘가 익숙한 이름이지 않은가? ㅎㅎ

 

 

재귀 함수란 간단히 말해서 자신을 정의할 때 자기 자신을 재참조하는 함수를 뜻한다.

재귀 함수를 배우기 앞서 대표적인 예시인 Factorial 함수를 구현해보자. Fatorial이 뭔지 모른다면 구글링을 통해 배우고 오자!

---

3. Factorial 기능을 구현하고 싶다.

3.1.

• 별도의 함수가 아닌 그냥 코드로 작성할 경우

int main()
{
  int i = 4;   // 4! 을 예시로 든다. 
  int iValue = 1; // 처음에는 1을 넣는다. 마지막에는 최종 결괏값이 들어간다.

  for ( int j = 0; j < i - 1; ++j)
  { 
    iValue *= (j + 2);
  }
}

가능하다. 하지만 나중에 또 사용할 때 또 코드를 작성하면 코드가 길어지고 지저분해진다.

 

- 기능을 함수로 만들어두면 재사용하기 편하다.

- 코드가 훨씬 간결해지고, 모듈화가 잘 되어 있으면 복잡한 기능을 만들고자 할 때 수월하게 만들 수 있다.

 

3.2.

• 함수로 코드를 작성한 경우

int Factorial(int count)
{
  int count = 1;   // 맨 처음 값

  for ( int j=0; j < count -1; ++j)
  { 
    count *= ( j + 2);
  }

  return count;
}

int main()
{
  int result = Factorial(4);  // 4! 의 값이 result에 담긴다.

  return 0;
}

3.3.

• 재귀 함수로 코드를 작성한 경우

//재귀함수 팩토리얼
int Factorial_re(int num)
{
  if (num == 1)
  return 1;
  return num * Factorial_re(num - 1);
}

int main()
{
  int result;
  result = Factorial_re(4);
  printf(" Factorial_re result: %d \n", result);
  return 0;
}