[자료구조] 재귀(순환)함수 recursion

1. 재귀(순환)이란?

- 재귀함수는 알고리즘이나 함수가 수행 도중 자기 자신을 호출하여 문제를 해결하는 기법이다.

 

- 재귀 함수는 자기 자신을 호출하였을 때 지금 자신의 정보인

   매개 변수, local data, return address 등을 stack에 저장한다.

   stack은 LIFO 즉 선입선출인 자료구조임으로 이를 이용해 호출 직전으로 돌아갈 수 있다.

 

<stack 영역 참고>

https://coding-ok.tistory.com/28

 

- 재귀 함수는 반드시 하나 이상의 if문을 가지고 있어야 한다.

   if문으로 함수의 재귀 호출을 계속할 것인지 혹은 그만둘 것인지를 결정한다.

   그렇지 않으면 무한히 자신을 호출하여 stack 메모리가 다 차는 stack overflow 오류가 발생한다.

 

- 모든 프로그래밍 언어가 재귀를 지원하는 것은 아니다. c는 지원한다.

 

2-1. 직접 재귀(direct recursion)

함수가 수행이 완료되기 전에 자기 자신을 다시 호출하는 것

A(n){
	A(n){
}

2-2. 간접 재귀(indirect recursion)

호출 함수를 다시 호출하게 되어 있는 다른 함수를 호출하는 것

A(n){
	B(n){
}

B(n){
	A(n){
}

 

3. 재귀는 언제 쓰나?

문제를 해결하는 알고리즘이 인수만 달리하고 자기 자신을 호출하는 순환적 구조일 경우에 적합하다.

예) 피보나치 수열, 이항계수, 이원 탐색, 하노이 탑 등

 

4-1. 재귀 예시 (1) 팩토리얼

※ 팩토리얼이란?

n >= 1 일 때, n! = n*(n-1)!

n! = n * (n-1) * (n-2) * ... * 1

예) 3! = 3 * 2 * 1 = 6

#include <stdio.h>

int fac(int num){
    if(num > 1){
        return num *= fac(num-1); //num이 1보다 크다면 num에다 num-1 값을 계속 곱한다.
    }else{
        return 1;
    }
}

int main(int argc, const char * argv[]) {
    printf("%d", fac(4));
}

<<내 코드>>

사실 맨 처음에 짰던 코드는 결과 변수를 전역으로 선언하여

결과 변수에 하나씩 곱하는 형태로 만들었다..

#include <stdio.h>

int result = 1; //결과 값을 저장할 변수를 전역으로 선언

int fac(int num){
    if(num > 1){
        result *= num; //결과 전역 변수에 num-1씩 곱해준다.
        return fac(num-1);
    }else{
        return num;
    }
}

int main(int argc, const char * argv[]) {
    fac(3);
    printf("%d", result);
}

 

보편적으로 팩토리얼 구현할 때는 전자를 많이 쓰는듯.

전자의 경우가 더 직관적이라고 생각한다.

 

4-2. 재귀 예시 (2) 피보나치

※ 피보나치란?

0  1  1  2  3  5  8  13  21  34  55  89  144 ...

세번째 항부터 첫번째 항과 두번째 항을 더한 값으로 이루어진 수열이다.

피보나치 수열의 초기값 f(0) = 0, f(1) = 1이고

f(i) = f(i-1)+f(i-2) (i>=2)이다.

#include <stdio.h>

int fibo(int num){
    if(num == 0){
        return 0;
    }else if(num == 1){
        return 1;
    }else{
        return fibo(num-1)+fibo(num-2);
    }
}

int main(int argc, const char * argv[]) {
    //피보나치 수열 20개 출력
    for(int i=0; i<20; i++){
        printf("%d ", fibo(i));
    }
}

 

4-3. 재귀 예시 (3) 최대공약수 - 유클리드 호제법

※ 최대공약수 구하는 방법

1) 일반적인 방법 :

입력한 두 수를 1이 아닌 공약수로 계속 나누어 나눈 공약수들을 모두 곱한다.

 

2) 유클리드 호제법 :

입력한 두 수 중에서 큰 수를 작은 수로 나눈 나머지를 구해서

나누는 수를 나머지로 계속 나눈다.

나머지가 0이 나오면 나누는 수가 최대공약수이고,

그렇지 않으면 계속해서 나머지가 0이 될 때까지 나눈다.

 

예) 1512, 1008의 최대공약수(gcd)

1512 / 1008 = 1 ... 504

1008 / 504 = 2 ... 0

따라서 504가 최대공약수이다.

#include <stdio.h>

int gcd(int a, int b){
    int remain;
    
    if(0 == (remain = a%b)){
        return b; //최대공약수
    }else{
        return gcd(b, remain);
    }
}

int main(int argc, const char * argv[]) {
     printf("%d", gcd(1008, 1512));
}