자료구조 (7), 재귀호출

재귀 호출

---

1. 재귀호출이란?

호출된 함수가 호출하는 함수와 동일한 함수

---

1) 개념

- 재귀함수를 구현하기 위해 탈출 조건(종료 조건)을 제대로 명시해줘야한다.

- 최초에 시작하는 초기항이 있어야한다. 이를 base case이라고 한다.

- 우리 목표에 도달할 때까지 식을 만들어서 적용하는 과정이 필요하다. 이를 재귀식 혹은 점화식을 잘 만들어야한다.

- factorial에서의 정의는 0!는 1로 가정한다. 하지만 이를 모두 체크하는 것이 아닌 number가 1이 될 때 1을 리턴하도록 해서 이를 표현할 수도 있다.

- 자기 자신을 우항 혹은 좌항에 놔두는 것을 재귀식이라고 한다

- 언젠가 n은 0이 되는 때가 등장하는데 이를 '점화식의 해 혹은 재귀식의 해'라고 한다.

2) 함수가 호출될 때

- 호출 블록에서 함수 코드로  제어 전환이 발생한다. 인자들 반환하고, 콜스택 공간 마련하고, 반환될 위치를 지정하는 등등의 동작이 수반된다.

- 함수가 호출되면 런타임 스택이 사용된다.

 

3) 꼬리 재귀 Tail Recursion

- 재귀 호출 중에 반복문으로 수정할 수 있는 경우에는 꼬리재귀(tail recursion)라고 한다. 이를 통해 연산 효율을 증가시킬 수 있다. 왜냐하면 함수 호출은 오버헤드를 발생시키기에 연산 효율이 좋지 않다. 따라서 꼭 필요한 경우에만 사용해야한다.

- 꼬리재귀: 반복되는 형태는 가장 마지막에 존재하고 지역변수는 따로 만들지 않는 것

- 재귀호출을 중복적으로 사용하지는 않는다. like 피보나치 수열은 f(n-1) + f(n-2)이기에 이는 꼬리 재귀가 아니다.

---

2. 재귀사항 구현 시 주의 사항

1) 개념

- 재귀 함수를 구현하기 위해 비재귀적인 방법으로 해결할 수 있는지, 작은 문제로 쪼갤 수 있는지 등 몇 가지를 체크해야한다.

- 재귀함수를 사용하는 것은 자연스러운 경우가 많다. 즉, 특정 요구사항에 맞게 동작할 때는 재귀함수가 더 유용하다. ex) RevPrint(listData)를 재귀호출을 사용한다면 뒷 요소부터 출력하는 것이 가능하다. 반복문으로 이를 구현하기는 쉽지 않다. 

- 꼬리재귀인 경우에는 반복문 형태로 치환하기 쉽지만 이를 일반적인 재귀는 반복문으로 구현하기 쉽지 않다.

- 재귀함수는 보기에 간단하지만 오버헤드가 발생하기에 적절하게 사용하는 것이 중요하다.

 

- base case(초기조건)는 작은 목록의 관점에서 해결책이 될 수 있다. 첫번째 스타트의 위치를 정할 수 있다.

- general case(일반 사례)는 점화식을 풀어서 base case에 더 가까이 다가가야한다. 

2) RevPrint 예시

- 넥스트가 null일 때까지 호출한 뒤, 리턴하여 출력하는 부분이 동작한다.

- 반복문으로 이를 구현하면 조금 복잡해지게된다.

- 탈출 조건을 설정하지 않으면 무한루프가 도는 것이 아니라 스택 오버플로우가 발생한다.

 

3) Function BinarySearch 예시

- fromLoc, toLoc를 전달해서 start, end 값을 지정한다.

- 검색을 했던 것 다음칸 혹은 이전칸의 범위에 대해 구현하는 것이 중요하다.

 

4) 재귀함수를 사용해도 괜찮은 경우

- 문제의 깊이가 문제의 크기보다 작은 경우, 즉 입력되는 단순한 식이 호출됐을 때에도 복잡하게 동작한다면 이는 재귀 형태로 작성하는 것이 좋지는 않다. like 아커만 함수는 적은 n을 입력하더라고 매우 복잡한 연산이 수반되고 이러한 경우에는 문제의 깊이가 있다고 볼 수 있다.

- 재귀호출의 깊이는 콜스택에 쌓여있는 호출을 의미한다고 볼수도 있다. like 인라인 함수는 실행 문장이 크지 않고, 작을 때만 좋다는 것과 유사하다.

- 재귀로 구현한다고 해서 연산 효율이 증가한다고 보기는 어렵다. 하지만 특정한 경우에는 재귀를 활용하는 것이 더 효율적이다.

---

3. 재귀함수 동작

1) Stack Activation Frames

 

2) Run-time stack activation records

 

- 스택이 쌓일수록 리턴어드레스가 바뀌어야한다.

 

- 리턴한 값이 호출한 부분에 반환이 된다.

 

 

 

cf) Quick sort 알고리즘

- 평균적으로는 다른 nlogn 시간복잡도를 가진 알고리즘보단 빠르지만 입력되는 데이터에 따라 최악의 경우에는 n^2의 복잡도를 가지게 된다. 오름차순으로 정렬된 경우 n * n-1 * n-2 ... 번을 탐색하기에 최악의 경우에 해당된다. 따라서 splitVal을 중앙값에 가깝게 뽑는 것이 좋다. 데이터의 크기가 큰 경우에는 3개를 뽑아 그 중 중간 값을 뽑아 splitVal로 하기도 한다.

- 요소를 하나 잡고, 그 요소를 기준으로 기준점보다 큰 값과 작은 값을 분류한다. 

- split function을 통해 알 수 있는 점은 매 iteration마다 splitVal의 위치를 알 수 있다. 또한 splitVal보다 작은 집합과 더 큰 집합을 확인할 수 있다.

- split function은 기준점인 splitVal에 대해 first, last를 순차적으로 이동시켜가며 splitVal보다 크거나 작은 경우 위치를 이동시켜준다.