[C] 팩토리얼과 유클리드 호제법의 재귀적 구현 및 꼬리 재귀 최적화

김태희·2023년 12월 12일

C 자료구조와 알고리즘

C로 배우는 자료구조와 알고리즘 시리즈

목록 보기

20/31

재귀란 ?

어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)이라고 한다.

자연수를 재귀적으로 정의하면 아래와 같다.

1. 1은 자연수이다.

2. 자연수 n의 바로 다음 수는 자연수이다.

이 조건 두 가지만으로도 1부터 2, 3, 4...와 같이 무한하게 이어지는 자연수를 정의할 수 있다.

재귀를 효과적으로 사용하면 프로그램을 간결하게 짤 수 있다.

팩토리얼 구하기

팩토리얼이란, 기호로 간단하게 n!로 나타내며 1부터 n까지의 자연수를 모두 곱하는 것을 의미한다.

음이 아닌 정수의 팩토리얼을 재귀적으로 정의하자면 아래와 같다.

1. 0! = 1

2. n>0 이면 n! = n * (n-1)!

위의 정의를 통해 함수를 구현해보자.

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int factorial(int n){
  if(n>0) return n * factorial(n-1);
  else return 1;
}

factorial 함수 내에서 자기 자신을 호출하면서 반복문 없이 간결하게 프로그램을 짤 수 있다.

직접 재귀와 간접 재귀

직접 재귀는 factorial 함수처럼 자기 자신과 같은 함수를 호출하는 구조로 이루어진다.

간접 재귀는 함수 a가 함수 b를 호출하고 함수 b가 함수 a를 다시 호출하는 구조, 즉 다른 함수를 통해 자기 자신과 같은 함수가 호출되는 식으로 이루어진다.

유클리드 호제법으로 최대 공약수 재귀적으로 구하기

유클리드 호제법은 두 양의 정수, 혹은 두 다항식의 최대공약수를 구하는 방법 즉 알고리즘이다.

호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다.

2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

#include <stdio.h>

int gcd(int x, int y){
  if(y==0) return x;
  else return gcd(y, x%y);
}

원래 유클리드 호제법에서는 a>b라는 조건이 있다.

하지만 C 언어에서는 2 % 3처럼 아예 나눌 수 없더라도 나머지를 구할 수 있다. (몫은 0 나머지는 2)

이 원리에 의해 a<b인 경우에도 아래의 예시처럼 첫 번째 재귀 연산을 통해 자동으로 a와 b의 자리가 바뀌게 된다.

a = 130, b = 80

130 80

80 50

50 30

30 20

20 10

10 10

10 0

--------------------------

a = 80, b = 130

80 130

130 80

80 50

50 30

30 20

20 10

10 10

10 0

반복문을 통한 factorial 함수와 gcd 함수 구현

#include <stdio.h>

int gcd(int x, int y){
  while(y!=0){
    int a = x;
    x=y;
    y = a%y;
  }
  return x;
}

int factorial(int n){
  int sum = 1;
  for(int i = n; i>0; i--){
    sum*=i;
  }
  return sum;
}

재귀 없이 위에서 구현했던 함수들을 구현해보았다.

확실히 재귀를 사용하였을때 변수의 개수도 줄고, 조건문과 반복문이 줄어들어 코드가 간결해졌다.

꼬리 재귀 최적화(tail recursion)

코드가 간결해지는 장점이 있는 반면, 재귀에는 단점도 존재한다.

재귀를 사용하면 지속적으로 함수를 호출하게 되면서 지역변수, 매개변수, 반환값을 모두 프로세스 스택에 저장하게 된다.

그 결과 반복문보다 메모리를 더 많이 사용하고 이는 속도 저하로 이어진다.

이를 해결하고자 사용하는 것이 꼬리 재귀이다. 꼬리 재귀란 반환값에서 추가 연산을 필요로 하지 않도록 하는 것이다.

재귀 함수에서는 자기 자신을 호출한 뒤 결과를 기다리면서 메모리가 낭비된다.

하지만 꼬리 재귀를 사용한다면 (꼬리재귀 최적화를 지원하는)컴파일러가 스택을 재사용할 수 있도록 알고리즘을 바꿔 재귀 호출이 끝나는 시점에서 아무 일도 수행하지 않고 바로 결과를 반환하게 된다.

아래의 예시를 살펴보자.

일반 재귀

int factorial(int n){
  if(n>0) return n * factorial(n-1);
  else return 1;
}
-------------------
결과

factorial(3)

3*factorial(2)

3*2*factorial(1)

6


--------------------


꼬리 재귀

int factorialTail(int n, int acc){	
  if (n == 1) return acc;	
  return factorialTail(n - 1, acc * n); 
}

int factorial(int n){	
  return factorialTail(n, 1);
}

--------------------
결과

factorialTail(3, 1)

factorialTail(2, 3)

factorialTail(1, 6)

6