[자료구조 스터디] 3. 자료구조와 재귀

[자료구조 스터디] 3. 자료구조와 재귀

1. 자료구조와 재귀

2. 재귀 구조의 예

---

1. 자료구조와 재귀

(1) 재귀(Recursion)는 내 안의 나를 찾는 것이다.

성격은 같지만, 크기만 작은 '나'를 찾아, 큰 나와의 관계를 드러내는 것이다.

이것도 재귀의 일종이다.

 

ex1. 팩토리얼

-팩토리얼(Factorial)은 자연수의 계승, 혹은 팩토리얼로 보인다. n이라는 자연수가 있다고 해보자. 이 자연수 n의 팩토리얼은 1부터 n까지의 모든 자연수의 곱을 뜻한다. 

-재귀=자기호출

---

2. 재귀 구조의 예

(1) 수열(Progression)

-등차수열(Arithmetic Progression)은 공차(앞뒤 숫자의 차이)가 같은 수열이다. (ex: 1,3,5,7,9..... /1,4,7,10,13...)

-Java-sequence(): sequence()는 순차적으로 정수값을 생성하는 객체이다.

 

-피보나치 수열(Fibonacci numbers): 피보나치 수열은 첫째 및 둘째 항이 1이고, 그 뒤의 모든 항이 바로 앞 두 항의 합인 수열이다. 

 

 

(2) 하노이 탑 문제 (Hanoi Tower Problem)

-하노이 탑 문제는 프랑스의 수학자 Edouard Lucas가 제시한 문제이다. 

 

-동판에 막대가 세 개 있고, 크기가 다른 4개의 원판이 첫번째 막대에 꽂혀 있다. 이 때,

(1) 한 번에 하나의 원판만 옮긴다.

(2) 크기가 큰 원판은 반드시 크기가 작은 원판 아래에 있어야 한다.

라는 조건이 있을 때, 원판을 모두 다른 막대로 옮기는 데 최소 몇 번을 이동해야 할까?

// 하노이 탑 알고리즘

move(n,a,b,c)
	if(n>0)
    	move(n-1,a,c,b)
        a에 있는 원반을 b로 옮긴다.
        move(n-1,c,b,a)

 

 

(3) 선택 정렬(Selection Sort)

-선택 정렬은 정렬 알고리즘 중에서 가장 기초적인 알고리즘이다.

   (1) 먼저 배열 중, 제일 첫번째 수와 맨 앞의 수를 바꾼다.

   (2) 그 다음엔 두번째로 작은 데이터를 선택해, 앞에서 두번째 데이터와 바꾼다.

   (3) 위의 과정을 반복한다.

=> "늘 가장 작은 것을 선택한다" => 선택 정렬(Selection sort)

 

-배열 a에 n개의 원소가 주어지고, 이 때 숫자들을 크기순으로 정렬하라고 한다면...

=> 이는 원소의 개수가 n-1,n-2,n-3...개인 배열의 문제들을 포함하고 있는 셈이다.

// 선택 정렬 알고리즘
SectioSort(A[],n): <-- 배열 A[0....n-1]을 정렬한다.
	for last <-n-1 downto 1
    A[0....last] 중 가장 큰 수 A[K]를 찾는다.
    A[K] <->A[last] <--A[K]와 A[last]의 값을 교환한다.

 

 

(4) 중위,후위,전위 표현법

-중위 표현법(Infix Expression)은 숫자와 숫자 사이에 연산자가 표현하는 것을 의미한다.  (ex: 1+1, 2-5...)

-전위 표현법(Prefix Expression) -> +11

-후위 표현법(Postfix Expression) -> 11+

중위 / 전위 / 후위 표현법의 예시