[자료구조] 06. 재귀 (Recursion)

재귀란?

▶ 알고리즘이나 함수가 실행 중에 자기 자신을 다시 호출하여 (함수 정의에서 자기 자신 호출 포함) 문제를 해결하는 기법이다. 정의 자체가 순환적으로 되어 있는 경우에 적합하다.

 

▶예시 : 팩토리얼 구현

https://pythontutor.com/c.html#mode=edit

int factorial(int n)
{
    if(n <= 1)
        return (1);
      
    else
        return (n * factorial(n-1));
}

< 팩토리얼 재귀 구현 코드>

ALGORITHYM factorial(n) // 알고리즘 이름
//Input : n (Integer; n >= 0)
//Output : n!

if n <= 1
     then return 1
                               // Base case = Escape condition (탈출 조건)
else
    return n * factorial(n-1)
                               // General case (일반적 정의)

< 팩토리얼 재귀 수도 코드>

 

    ▷모든 재귀 알고리즘은 2 part로 나뉜다.

       1)  Base Case (= Escape Condition) : 탈출 조건

            → 탈출 조건이 없다면 시스템 오류가 발생할 때까지 무한 호출하게 된다.

       2)  General Case : 일반적 정의

---

재귀(Recursion) vs 반복(Iteration)

▶ 재귀는 자신을 호출(copy)하고, 반복은 loop를 사용한다. (for, while문을 이용하여 반복)

    ▷팩토리얼로 비교

int factorial_iterative(int n)
{
  int i, result = 1;

  for(i = n; i>.; i++)
     result = result * i;
   
  return result;
 }

<팩토리얼 반복 구현 코드>

 

     ▷거듭제곱 구하기로 비교

ALGORITHM power(x,n)
//Input : x,n
//Output : x^n

if n==0
	then return 1
                    //Base Case (탈출 조건)
                    
else if n%2 == 0    // n이 짝수일 경우
	then return power(x*x,n/2);
  
else if n%2 == 1    //n이 홀수일 경우
	then return x*power(x*x, (n-1)/2);

<거듭제곱 구하기 재귀 수도 코드>

double power(double x, int n)
{
	if(n==0)
    	return 1;
        
    else if((n%2)==0)                  // n is even number
    	return power(x*x, n/2);
        
    else                               // n is odd number
    	return x*power(x*x, (n-1)/2);
}

<거듭제곱 구하기 재귀 구현 코드>

double power_iter(double x, int n)
{
	int i;
    double result = 1.0;
    
    for( i=0; i<n ; i++)
    	result = result * x;
        
    return result;
}

<거듭제곱 구하기 반복 구현 코드>

     

    ▷ 거듭제곱 구하기에서 시간 복잡도 비교 : 재귀 O(log n) < 반복 O(n)  

 

---

재귀 대표 예시

▶ 피보나치수열 계산 : 순환을 이용하면 비효율적인 대표적인 예시이다.

                               → 같은 항이 중복 계산됨. n이 커지면 더 심해짐.

ALGORITHM fib(n)
//Input : n (양의 정수)
//Output : 피보나치 수열의 n번째 값

if(n==0)
	return 0;
    
if*n==1)
	return 1;
    
    return (fib(n-1) + fib(n-2));

< 피보나치수열 계산 수도 코드>

fib(6)을 호출하면 fib(3)이 4번이나 중복 계산된다.

 

▶ 하노이탑 : 막대에 A에 쌓여있는 n개의 원판을 막대 C로 옮기는 문제

                   → 한 번에 하나의 원판만 이동 가능.

                   → 맨 위의 원판만 이동 가능.

                   → 크기가 작은 원판 위에 큰 원판이 쌓일 수 없음.

ALGORITHM HanoiTower(n, start, temp, goal) <- (4개의 매개변수)
// Input : n(원반 갯수), start(시작 기둥), temp(중간 기둥), goal(목표 기둥);
// 원반은 1,2,3,...,n으로 증가하는 크기 순서
// Output : 화면에 옮기는 과정을 출력

if(n=1)
	print("MOVE DISC n FROM start TO goal")
                                               //Base Case (탈출조건)

else
    HanoiTower( n-1 , start , goal , temp )
    print("MOVE DISC n FROM start TO goal")
    HanoiTower( n-1 , temp , start , goal )

< 하노이탑 수도 코드>

#include <stdio.h>

void Hanoi(int, char, char, char);

int main(void)
{
	
    int n = 3;     // n = 3일때
    
    Hanoi(n,'A','B','C');
    
    return 0;
    
}

void Hanoi(int n, char start, char temp, char goal)
{
	
    if (n==1)
    	printf("Move disc %d from %c to %c\n", n, start, goal);
        
	else
    {
    
    	Hanoi(n-1, start, goal, temp);
        printf("Move disc %d from %c to %c\n", n, start, goal);
        Hanoi(n-1, temp, start, goal);
        
    }
    
}

< 하노이탑 코드>

---

참고 서적 : <C언어로 쉽게 풀어쓴 자료구조>