Chapter 02. 재귀(Recursion)

김민정·2024년 10월 10일
c언어개발기술블로그알고리즘자료구조재귀코딩
1

윤성우 열혈 자료구조

목록 보기
2/14
post-thumbnail

02-1. 함수의 재귀적 호출의 이해

재귀는 자료구조와 알고리즘에 있어서 매우 중요한 요소이고, C언어는 재귀를 지원하는 언어다.
열혈 c프로그래밍에서 재귀의 동작방식을 이해하는데 중점을 두었다면 이번에는 재귀의 적용을 중심으로 배울 것이다.

재귀함수의 기본적인 이해

C 프로그래밍에서 배운 재귀함수를 다시 한번 살펴보자.

  • 재귀함수의 호출 원리

    재귀함수란? 함수 내에서 자기 자신을 다시 호출하는 함수를 의미한다.
    위 그림에서 Recursive 함수가 호출되면, Recursive 함수의 복사본이 만들어져서 복사본이 실행되는 구조로 재귀함수의 호출을 설명하고 있다.
    Recursive 함수를 실행하는 중간에 다시 Recursive 함수가 호출되면, Recursive 함수의 복사본을 하나 더 만들어서 복사본을 실행하게 된다.
    실제로 함수를 구성하는 명령문은 CPU로 이동이 되어서(복사가 되어서) 실행이 된다. 그런데 이 명령문은 얼마든지 CPU로 이동(복사)이(가) 가능하다. 따라서 Recursive 함수의 중간쯤 위치한 명령문을 실행하다가 함수의 실행을 완료하지 않은 상태에서 다시 Recursive 함수의 앞 부분에 위치한 명령문을 CPU로 이동시키는 것은 문제가 되지 않는다.
    다음 예제를 통해 재귀의 탈출조건을 추가해서 재귀에 대해 이해해보자.

#include <stdio.h>

void Recursive(int num)
{
    if (num <=0)
        return;
    printf("Recursive call! %d\n", num);
    Recursive(num - 1);
}

int main()
{
    Recursive(3);
    return 0;
}

> 출력
Recursive call! 3
Recursive call! 2
Recursive call! 1

위에서 재귀의 탈출조건으로 Recursive(0)이 되면서 함수가 반환하기 시작한다.

재귀함수의 디자인 사례

재귀함수는 자료구조나 알고리즘의 어려운 문제를 단순화하는데 사용되는 중요한 도구이다.
무엇보다도 재귀함수가 있기에 재귀적인 수학적 수식을 그대로 코드로 옮길 수 있다.
이러한 재귀함수의 특징을 보여주는 사례가 팩토리얼(factorial)값을 반환하는 함수이다.

위 그림에서 보듯 정수 n 팩토리얼은 정수 n과 n-1 팩토리얼의 곱으로 표현할 수 있으며 n 팩토리얼 f(n)f(n)은 수식적으로 다음과 같이 표현할 수 있다.

이를 코드로 옮기게 되면 아래와 같이 표현할 수 있다.

if(n==0)
	return 1;
else	// n>=1의 경우
	return n*Factorial(n-1);

예제로 정리해서 실제로 잘 작동하는지 확인해보자.

#include <stdio.h>

int Factorial(int n)
{
    if(n==0)
        return 1;
    else
        return n*Factorial(n-1);
}

int main()
{
    printf("1! = %d\n", Factorial(1));
    printf("2! = %d\n", Factorial(2));
    printf("3! = %d\n", Factorial(3));
    printf("4! = %d\n", Factorial(4));
    printf("9! = %d\n", Factorial(9));
    printf("0! = %d\n", Factorial(0));
    
    return 0;
}

> 출력
1! = 1
2! = 2
3! = 6
4! = 24
9! = 362880
0! = 1

02-2. 재귀의 활용

재귀함수는 이해하는 것도 중요하지만 잘 정의하는 것도 중요하다.
재귀함수를 잘 정의하기 위해서는 사고의 전환이 필요하다.

피보나치 수열: Fibonacci Sequence

피보나치 수열은 재귀적인 형태를 띠는 대표적인 수열로서 다음과 같이 전개된다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ....

'앞에 값 두 개를 더해서 현재의 수를 만들어가는 수열'이 피보나치 수열이다.
수열의 nn번째 값 == 수열의 n−1n-1번째 값 ++ 수열의 n−2n-2번째 값

피보나치 수열의 nn번째 위치의 값을 반환하는 함수의 수학적 표현은 다음과 같다.

이를 코드로 옮겨보자.

int Fibo(int n)
{
	if(n==1)
    	return 0;
    else if(n==2)
    	return 1;
    else
    	return Fibo(n-1) + Fibo(n-2);
}

코드로 잘 옮겨졌는지 다음 예제를 통해 알아보자.

#include <stdio.h>

int Fibo(int n)
{
    if(n==1)
    	return 0;
    else if(n==2)
    	return 1;
    else
    	return Fibo(n-1) + Fibo(n-2);
}

int main()
{
    int i;
    for(i=1; i<15; i++)
        printf("%d ", Fibo(i));
    
    return 0;
}

> 출력
0 1 1 2 3 5 8 13 21 34 55 89 144 233

위 예제를 함수의 호출순서에 대해 이해하기 위해서 약간의 코드를 수정해보자.

#include <stdio.h>

int Fibo(int n)
{
    printf("func call param %d \n", n);

    if(n==1)
    	return 0;
    else if(n==2)
    	return 1;
    else
    	return Fibo(n-1) + Fibo(n-2);
}

int main()
{
    Fibo(7);
    return 0;
}

> 출력
func call param 7 
func call param 6
func call param 5
func call param 4
func call param 3
func call param 2
func call param 1 
func call param 2
func call param 3
func call param 2
func call param 1
func call param 4
func call param 3
func call param 2
func call param 1
func call param 2
-----------------
func call param 5
func call param 4
func call param 3
func call param 2
func call param 1
func call param 2 
func call param 3
func call param 2
func call param 1

출력을 보면 알 수 있듯 재귀함수는 매우 많은 수의 함수호출을동반한다. 피보나치 수열의 7번째 값의 출력을 위해서도 25회의 함수호출이 동반되었다.

위 그림이 출력에서 점선 위까지의 호출을 도식화 한 것이다.

이 그림이 점선 아래에 해당하는 부분이다.

이렇게 호출순서를 정리하는 것은 큰 의미가 없기 때문에 재귀함수 자체를 이해하는 것이 좋다.

이진 탐색 알고리즘의 재귀적 표현

이번에는 Chapter 01에서 구현한 이진 탐색 알고리즘을 재귀함수 기반으로 재구현해보려 한다.
먼저, 이진 탐색 알고리즘의 반복 패턴을 정리해보자.

  1. 탐색 범위의 중앙에 목표 값이 저장되었는지 확인
  2. 저장되지 않았다면 탐색 범위를 반으로 줄여서 다시 탐색 시작

그리고 탐색의 실패가 결정되는 시점은 first(탐색 시작 위치)가 last(탐색 범위의 끝)보다 커지는 경우다.
탈출조건을 먼저 코드로 정리해보자.

int BSearchRecur(int ar[], int first, int last, int target)
{
	if(first > last)
    	return -1;		// -1의 반환 = 탐색의 실패
}

그리고 탐색 알고리즘의 반복 패턴 1인 "탐색 범위의 중앙에 목표 값이 저장되었는지 확인"하는 코드를 넣어본다.

int BSearchRecur(int ar[], int first, int last, int target)
{
	int mid;
    
	if(first > last)
    	return -1;
        
    mid = (first+last)/2;	// 탐색 대상의 중앙 찾기.
    if(ar[mid]==target)
    	return mid;			// 탐색된 타겟의 인덱스 값 반환.
}

그리고 그 다음 반복 패턴인 "저장되지 않았다면 탐색 범위를 반으로 줄여서 다시 탐색 시작" 코드를 삽입해보자.

int BSearchRecur(int ar[], int first, int last, int target)
{
	int mid;
    
	if(first > last)
    	return -1;
        
    mid = (first+last)/2;	// 탐색 대상의 중앙 찾기.
    if(ar[mid]==target)
    	return mid;			// 탐색된 타겟의 인덱스 값 반환.
    else if(target < ar[mid])
    	return BSearchRecur(ar, first, mid-1, target);
    else
    	return BSearchRecur(ar, mid+1, last, target);
}

여기서 추가된 부분 return BSearchRecur(ar, first, mid-1, target);와 return BSearchRecur(ar, mid+1, last, target);이 재귀의 핵심이다.

실제로 탐색이 잘 이루어지는지 다음 예제를 통해 알아보자.

#include <stdio.h>

int BSearchRecur(int ar[], int first, int last, int target)
{
	int mid;
    
	if(first > last)
    	return -1;		    // -1의 반환 = 탐색의 실패
        
    mid = (first+last)/2;	// 탐색 대상의 중앙 찾기.
    if(ar[mid]==target)
    	return mid;			// 탐색된 타겟의 인덱스 값 반환.
    else if(target < ar[mid])
    	return BSearchRecur(ar, first, mid-1, target);
    else
    	return BSearchRecur(ar, mid+1, last, target);
}

int main()
{
    int arr[] = {1, 3, 5, 7, 9};
    int idx;

    idx = BSearchRecur(arr, 0, sizeof(arr)/sizeof(int)-1, 7);
    if(idx==-1)
        printf("탐색 실패 \n");
    else
        printf("타겟 저장 인덱스: %d \n", idx);

    idx = BSearchRecur(arr, 0, sizeof(arr)/sizeof(int)-1, 4);
    if(idx==-1)
        printf("탐색 실패 \n");
    else
        printf("타겟 저장 인덱스: %d \n", idx);

    return 0;
}

> 출력
타겟 저장 인덱스: 3 
탐색 실패

02-3. 하노이 타워: The Tower of Hanoi

하노이 타워 문제는 '하나의 막대에 쌓여 있는 원반을 다른 하나의 원반에 그대로 옮기는 방법'에 관한 것이다. 이때 조건이 있다. 원반은 한 번에 하나씩만 옮길 수 있고, 옮기는 과정에서 작은 원반 위에 큰 원반이 올려질 수 없다는 것이다.
그래서 막대는 3개로 이루어져 있고 간단하게 3개의 원반을 옮기는 과정은 다음과 같다.





3개의 원반은 이렇게 생각하기 쉽지만 이 갯수가 많아진다면 어려워진다.

하지만, 문제의 해결을 위해 생각해보면 3번 원반을 c로만 옮기기 위해 1, 2번 원반을 B 막대로 옮길 수 만 있다면 문제는 해결이 된다.

하노이 타워의 반복패턴 연구

그럼 이번엔 원반 4개를 생각해보자.

A 막대에서 원반 4개를 C 막대로 옮기기 위해서는 1, 2, 3원반을 우선 B막대로 옮겨야한다.

그 다음 1, 2, 3원반을 C막대로 옮기면 된다. 이를 일반화해서 막대 A에 꽂혀있는 원반 nn개를 막대 C로 옮기는 과정을 정리해보자.

  1. 작은 원반 n-1개를 A에서 B로 이동
  2. 큰 원반 1개를 A에서 C로 이동
  3. 작은 원반 n-1개를 B에서 C로 이동

하노이 타워 문제의 해결

위에서 정리한 과정을 코드로 나타내보자.
우선 num개의 원반을 by를 거쳐서(by를 이용해서) from에서 to로 이동한다.

// from에 꽂혀있는 num개의 원반을 by를 거쳐서 to로 이동
void HanoiTowerMove(int num, char from, char by, char to)
{
	...
}

탈출 조건으로는 원반이 1개일 때 from에서 to로 이동시키면 된다.

// from에 꽂혀있는 num개의 원반을 by를 거쳐서 to로 이동
void HanoiTowerMove(int num, char from, char by, char to)
{
	if(num==1)	// 이동할 원반의 수가 1개
    {
    	printf("원반1을 %c에서 %c로 이동 \n", from , to);
    }
    else
    {
    	...
    }
}

그 다음 작은 원반 n−1n-1개를 A에서 B로 이동을 코드로 추가해보자.

// from에 꽂혀있는 num개의 원반을 by를 거쳐서 to로 이동
void HanoiTowerMove(int num, char from, char by, char to)
{
	if(num==1)	// 이동할 원반의 수가 1개
    {
    	printf("원반1을 %c에서 %c로 이동 \n", from , to);
    }
    else
    {
    	HanoiTowerMove(n-1, from, to, by);	// 3단계 중 1단계
    }
}

위에서 to 인자가 by로 전달되고, by인자가 to로 전달되고 있다. 이는 n−1n-1개의 원반을 A에서 B로 우선 이동시켜야하기 때문이다.
그 다음 큰 원반 1개를 A에서 C로 이동하는 코드, 작은 원반 n−1n-1개를 B에서 C로 이동하는 코드를 추가해보자.

// from에 꽂혀있는 num개의 원반을 by를 거쳐서 to로 이동
void HanoiTowerMove(int num, char from, char by, char to)
{
	if(num==1)	// 이동할 원반의 수가 1개
    {
    	printf("원반1을 %c에서 %c로 이동 \n", from , to);
    }
    else
    {
    	HanoiTowerMove(num-1, from, to, by);	// 3단계 중 1단계
        printf("원반%d을(를) %c에서 %c로 이동 \n", num, from, to);	// 3단계 중 2단계
        HanoiTowerMove(num-1, by, from, to);	// 3단계 중 3단계
    }
}

이로써 하노이 타워의 문제를 해결하는 재귀함수가 완성이 되었다.
다음 예제에서 잘 작동하는지 확인해보자.

#include <stdio.h>

void HanoiTowerMove(int num, char from, char by, char to)
{
	if(num==1)	// 이동할 원반의 수가 1개
    {
    	printf("원반1을 %c에서 %c로 이동 \n", from , to);
    }
    else
    {
    	HanoiTowerMove(num-1, from, to, by);	// 3단계 중 1단계
        printf("원반%d을(를) %c에서 %c로 이동 \n", num, from, to);	// 3단계 중 2단계
        HanoiTowerMove(num-1, by, from, to);	// 3단계 중 3단계
    }
}

int main()
{
    // 막대 A의 원반 3개를 막대 B를 경유해서 막대 C로 옮기기
    HanoiTowerMove(3, 'A', 'B', 'C');
    return 0;
}

> 출력
원반1을 A에서 C로 이동 
원반2을(를) A에서 B로 이동 
원반1을 C에서 B로 이동
원반3을(를) A에서 C로 이동
원반1을 B에서 A로 이동
원반2을(를) B에서 C로 이동
원반1을 A에서 C로 이동

<Review>

이렇게 c언어로 재귀함수까지 알아봤다.
python으로 할 때보다 이해가 더 빨리 되는 것은 언어가 단순해서 그런가...
아니면 두 번째로 배워서 그런가...
오늘도 알차고 재밌었다!

profile
김민정
백엔드 코린이😁
이전 포스트

Chapter 01. 자료구조와 알고리즘의 이해

다음 포스트

Chapter 03. 연결 리스트(Linked List) 1

0개의 댓글