자료구조 강의 2장 - 재귀와 백트래킹

해당 포스팅은 pc에서 작성

건국대학교 KOCW 자료구조 강좌를 들으면서 필기

4강 약 30분 ~5강 약 35분

재귀함수(Recursion)

자기 자신을 호출하는 함수

 

재귀 단계(Recursion step)

자신의 복사본을 호출하여 더 작은 문제를 풀게 하여 문제를 해결

 

재귀 단계는 더 많은 재귀 단계 생성 가능

중요: 원하는 역할을 수행한 뒤 재귀가 확실히 종료하게 해야 한다

 

매 단계마다 원본 문제보다 조금 더 단순한 문제에 자기 자신을 호출

작은 문제의 서열은 결국 기본 경우(base case)로 수렴

 

복잡한 문제를 한번에 해결하려 하지 않고

쪼개서 단순하게 부분부분 해결하는 과정을 표현한 것

 

예) 팩토리얼 함수, 피보나치 수열, 하노이의 탑 예제, 병합 정렬, 퀵 정렬 등

 

팩토리얼 함수

n! 은 n과 1 사이의 모든 정수의 곱

 

0! = 1

1! = 1* 0! = 1

.

.

.

n! = n * (n-1)!

 

이를 함수로 표현하면 아래와 같다

int Factorial(int n)
{
    // 0!, 1!은 1
    if(n==0)
    	return 1;
    else if(n==1)
    	return 1;
    // 재귀 n-1팩토리얼에 n을 곱하기
    else
    	return n*factorial(n-1);
}

 

재귀 경우 (recursion step) : 점점 작은 n에 대한 팩토리얼을 부르다

기본 경우 (base case) : 결국 0!이나 1!으로 자기 자신을 호출하지 않고 끝난다

 

 

팩토리얼을 재귀함수를 쓰지 않고 푼다면,

반복(Iteration)을 사용하여 풀 수도 있다

 

수행 시간상으로는 반복 함수가 빠름

컴파일러가 일부 재귀함수를 반복함수로 변형하여 풀기도 함

= 재귀적으로 풀 수 있는 문제는 보통 반복적으로도 풀 수 있다

int Factorial(int n)
{
    int tmp = 1;
    for(int i=1; i<=n; i++)
    {
    	tmp *= i;
    }
    return tmp;
}

해당 코드와 같이 루프를 사용해서도 해결이 가능

 

 

 

재귀 호출될 때마다 메서드(함수, function)의 복사본(실제로는 메서드 내 지역 변수만)이 메모리에 생성

메서드를 종료할 때(데이터 리턴) 시, 리턴하는 메서드의 복사본은 메모리에서 삭제

 

메모리는 공간. 각 공간에 주소

32비트 = 0 ~ 2^32-1

 

처음 만든 재귀 함수 factorial(int n)에 main()을 더해 이를 수행하는 exe 파일을 실행했다면

main()

Factorial(int n) + n값, 리턴값, 지역 변수

Factorial(int n-1)

Factorial(int n-2)

.

.

.

↑

Global Variable (글로벌 변수)

Factorial.exe

 

위 스택 1칸을 스택 프레임(frame)

 

malloc (memory allocation, 메모리 할당)

위에서부터 써주는 것도 있고, 아래에서부터 써주는 것도 있음

Stack 영역 : main() > factorial 재귀함수 위에서 밑으로 쌓임

heap 영역 : 아래에서부터  위로 쌓음 

 

메모리에 이와 같은 형태로 할당

 

 

 

두번째로 만든 반복함수를 실행했다면,

main()

Factorial(int n) + n값, 리턴값, 지역 변수들

.

.

.

.

.

↑

Global Variable (글로벌 변수)

Factorial.exe

추가로 함수를 호출하지 않기에 함수 자체는 처음 할당한 메모리 그대로 유지

 

 

그래서, 재귀와 반복 중 어떤 것이 나은가?

어떤 것을 하려는지에 따라 다름

 

1) 재귀

특정한 어려운 문제를 수학적으로 쉽게 풀 수 있게 해준다

어떤 문제들에 대한 해답은 재귀적으로 수식을 세우기가 쉽다

재귀는 매번 수행하는 재귀 호출에 부가적인 요소들이 추가(스택 공간 필요)

기본 경우를 제대로 고려하지 않아 무한 재귀에 들어가면 스택이 계속 쌓임

>아래의 heap영역과 만나고 메모리 용량 초과

> 스택 오버플로우 초래

> 프로그램 종료

 

2) 반복

조건이 거짓이 되면 종료

각 반복이 부가 공간을 필요로 하지 않음

무한 루프는 추가 메모리가 필요하지 않으므로 무한히 반복

(메인 함수에서 돌리면 프로그램이 계산하고 다음으로 넘어가지 않아 프리즈되긴 해도 꺼지진 않았음)

어떤 문제들의 경우에는 눈에 띄는 반복적 알고리즘이 없을 수도 있다

 

 

많은 얘기가 있었지만 1문장으로 정리해서,

보통은 연산 속도가 빠른 반복으로 풀다가

반복으로 규칙을 정해 풀기 힘든 문제가 있다면 재귀로 풀어보자

 

 

다른 예제로 재귀함수의 예시로 유명한

하노이의 탑

일렬로 늘어선 막대 3개가 있고

보통은 왼쪽에 있는 하나의 막대에 크기가 각각 다른 링이 n개 꽂혀 있음

 

목적: 링을 제일 오른쪽에 있는 막대에 모두 옮기기

제약: 한번에 하나씩 이동할 수 있고, 크기가 큰 링은 작은 링 위에 얹을 수 없음

 

알고리즘은 아래와 같다

• 재귀 단계

막대를 왼쪽부터 A, B, C(타겟) 라고 하면

1. n-1개를 A로부터 B로 옮긴다
2. 제일 큰 링을 C로 옮긴다
3. n-1개를 B에서 C로 옮긴다

이 재귀 단계를 점점 수행하게끔 하면 된다

 

• 기본 경우

n=1일 때, 그냥 A에서 C로 옮기면 끝

 

굵은 글씨인 기본 경우,  재귀 단계들을 수식으로 옮기면

 

floor = n

from = A = 왼쪽을 기준으로 첫째 막대,

tmp = B = 둘째 막대,

to = C =  셋째 막대 

void com(int from,int tmp, int to,int floor)
{
	if (floor == 1)
		move_of_block(from, to);
	else
	{
		com(from, to, tmp,floor - 1);
		move_of_block(from, to);
		com(tmp, from, to, floor - 1);
	}
}

move_of_block(int a, int b)

a번째 막대의 가장 위의 링 1개를  b번째 막대로 이동

+ 이를 시각적으로 보여주게끔 구현

 

메서드 코드 길이가 길고

공부 내용이랑은 동떨어지는 부분이 있기에

대충 어떤 기능을 하는지만 기술

 

코드 전문은 아래 url 참조

https://ybbro.tistory.com/79

C) 하노이의 탑 cmd 창에서 게임으로 즐기기 (exe, 소스 코드 첨부)

 

 

백트래킹(Backtracking)

강의에 설명이 없었으나 개념만 정리하자면

모든 경우의 수 탐색하면서 막히면 뒤로 다시 돌아가서 다시 해를 찾기

 

비슷한 예제로 게임을 예전에 작성한 적 있기는 하나

경우의 수를 다 따져서 한 것이라 너무 비효율적이었다..

 

강의를 듣다 나오면 추가 예정