JAVA 자료구조(재귀와 귀납적 사고) - 자료구조와 재귀, 재귀 구조 예

 

1.자료구조와 재귀

그림 2-1 내 안에 나와 똑같지만 크기만 작은 것이 포함된 예

 

재귀는 '내 안의 나를 찾는 것'이다. 즉, 성격은 같고 크기만 작은 나를 찾아 큰 나와 작은 나가 연결된 관계를 드러내는 것이다. 단순한 예로 시작해보자.

 

1부터 n까지 곱하는 n!(n 팩토리얼)은 n! = 1 x 2 x 3 x ... x(n - 1) x n 이다. 여기서 맨 끝에 있는 n만 제외하면 1 x 2 x 3 x ... x (n -1)인데 이것은 (n - 1)!이다. n!은 여기에 n만 더 곱하면 된다. 즉, n! = n x (n - 1)이다. 크기가 n인 팩토리얼은 크기가 n -1인 팩토리얼을 포함하고 있다. 이 처럼 어떤 문제나 함수 등이 자신과 선격이 똑같지만 크기가 더 작은 문제를 하나이상 포함하고 있을 때 재귀적 구조를 작고 있다고 말한다.

 

대부분의 프로그래밍 언어는 함수 내부에서 자신을 호출하는 자기호출 기능을 제공한다. 영어로는 recursion이라고 하고 우리말고는 보통 재귀라고 하는데, 재귀라는 용어가 직관적으로 와닿지 않아 보다 직관적인 용어인 '자기호출'과 섞어 쓸 것이다. 이런 의미에서, 자료구조와 알고리즘은 관계 중심의 사고방식을 훈련하는 도구이기도 하다.

 

재귀는 컴퓨터 과학 이론의 근간을 이루는 중요 개념으로, 어렵거나 특별한 주제가 아니다. 컴퓨터 과학을 공부하다 보면 재귀는 끊임없이 다양한 얼굴로 출현한다. 따라서 이 주에에 대해 숨 쉬듯이 자연스럽게 받아들이는 것이 좋다.

 

재귀와 관련된 훈련은 고등수학과정에서 부터 접할 수 있는데 수열의 점화식이 재귀적 표현의 예다. 수학적 귀납법도 이 틀에 속한다.

 

2. 재귀 구조 예

1. 수열

https://www.youtube.com/watch?v=5cYZX47w7gQ

 

 

등차수열의 재귀적 연산

위 는 초항이 1이고, 공차가 3인 등차수열의 점화식이다.

알고리즘 seq(n)은  seq(n-1)을 호출하고, seq(n-2)를 호출하고, seq(n-2)는 seq(n-3)을 호출하고,... seq(2)는 seq(1)을 호출하고, seq(1)은 1을 리턴하고 끝난다.  seq(1)이 끝나면 역순으로 진행된다. seq(2)는 seq(1)의 리턴 값을 받아 3을 더해 리턴하고, seq(3)은 seq(2)의 리턴 값을 받아 3을 더해 리턴하고, seq(4)는 seq(3)의 리턴 값을 받아 3을 더해 리턴하고, ...., seq(n)은 seq(n-1)의 리턴 값을 받아 3을 더해 리턴하면서 전체가 끝난다.

 

등차수열은 결과를 바로 계산할 수 있는 식이 있어 굳이 이렇게 구할 필요하 업지만 그 속에 재귀적 구조가 있음을 말하려는 것이다. 재귀 알고리즘은 반복해서 호출하다 언제가 끝나야 하는데 이를 위한 경계조선을 항상 갖고있어야 한다. [알고리즘 2-1]에서는 if(n = 1)이 경계 조건이다. 수열의 초항이다.

 

 

피보나치 수열의 재귀적 연산

피보 나치 수열은 위와 같다. 즉, 첫 두 항은 1이고, 나머지 항은 각각 직전 두항을 더한 값이다. 

피보나치 수열을 재귀 알고리즘으로 구현하면 [알고리즘 2-2]와 같다. 피보나치 수열은 재귀 알고리즘으로 구현한 치명적인 예다.  연산하는데 시간이 너무 많이 걸리기 때문이다. 100번째 피보나치 수를 계산하기 위해 [알고리즘 2-2]의 fib(100)을 수행하면 평생을 기다려도 결과를 볼 수 없다. 보통 가정집 사양의 PC로 수행하면 fib(50)은 36초 가량이 걸린다. fib(66)은 하루 정도 걸리고, 추산해본 결과 fib(100)이 끝나려면 3만 5천 년 정도 걸린다. fib(136)부터는 1조 년을 넘어 선다. 지수함수적으로 증가한다는 느낌은 이런 것이다. 

 

이렇게 엄청난 시간이 걸리는 이유는 한 번 계산해놓은 결과를 계속 호출하여 지수함수적인 중복을 일으키기 때문이다. 

 

피보나치 수열의 비재귀적 연산

같은 피보나치 수열을 [알고리즘 2-3]과 같이 계산하면 fib_fast(100)은 천 만분의 1초도 걸리지 않는다. 재귀는 문제를 해겨하는 유용한 도구이지만 잘못 쓰면 치명적이다. 자료구조와 알고리즘에서는 주로 재귀가 유요할 경우에 사용한다.

 

💡 tip) 피보나치 수열

첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 
ex) 1, 1, 2, 3, 5, 8, 12, .... 

 

2. 하노이 탑

https://vidkidz.tistory.com/649

하노이의 탑 (Tower of Hanoi)

그림 2-2 원반이 4개인 하노이 탑 문제

• 원반은 한 번에 하나씩 옮길 수 있다.
• 큰 원반이 작은 원반 아래에 놓여 있어야 한다.

하노이 탑은 아마도 가장 유명한 재귀성을 가진 문제 중 하나일 것이다. a, b, c 3개의 기둥이 있고, 기둥 a에 넓이가 서로 다른 n개의 원반 n개의 원반이 있다. 이 n개의 원반을 기둥 b로 옮겨야 하는데 아래 규칙을 만족하면서 옮겨야 한다. 기둥 c는 중간에 원반(들)을 임시로 옮겨두는 보조 기둥으로 사용한다. [그림 2-2]는 원반이 4개인 하노이 탑 문제의 예다. 

 

 

[그림 2-2]와 같은 하노이 탑 문제를 푸는 알고리즘은 [알고리즘 2-4]와 같다. [알고리즘 2-4]에서 기둥 a에 있는 n개의 원반을 기둥 b로 옮기는 작업을 차례호 살펴보자.

 

ⅰ) 맨 아래 원반을 제외한 나머지 n-1개의 원반을 기둥 c로 옮긴다.(2️⃣)

ⅱ) a에 남은 원반 1개를 b로 옮긴다.(3️⃣)

ⅲ) c로 옮겨둔 n-1개의 원반을 b로 옮긴다.(4️⃣)

 

크기 n인 하노이 탑 문제가 크기 n-1인 하노이 탑 문제 2개(2️⃣와4️⃣)를 포함하고 있다. 그 둘 사이에 크기 1인 하노이 탑 문제가 하나(3️⃣) 끼어 있다. 1️⃣은 경계 조건이다. 크기 n인 문제로 시작해서 점점 작은 문제를 호출해가다가 언제가는 끝나야 한다. 1️⃣은 크기가 0이 되면 끝내라는 뜻이다. 크기가 0인 문제는 실제로 존재하지 않는 문제인데, 위와 같은 경계조건이라면 크기 0일 때는 아무 일도 하지 않고 move(0,..)이 호출되자마자 바로 끝난다.

 

하나만 더 살펴보자. [알고리즘 2-2]의 마지막 직전 단계는 move(1,...)이 호출되어 다음과 같이 수행된다.

2️⃣와 4️⃣에서 move(0, ...)이 호출되면 이들은 들어가자마자 1️⃣의 if(0>0)에 걸려 그냥 빠져나온다. 맨 마지막 단계에서는 모두 이 과정을 거쳐서 자기 호출을 종료하게 되는데 move(n,a,b,c)를 수행하는 과정에서 move(0,...)이 총 2ⁿ-1번 이나 호출된다. 어마어마 하게 많은 횟수이다.

 

 

 

[출처 - 쉽게 배우는 자료구조 with 자바,  저 문병로]
https://www.hanbit.co.kr/store/books/look.php?p_code=B7033044159

IT CookBook, 쉽게 배우는 자료구조 with 자바