[자료구조] Recursion 재귀

Recursion
: when a method call itself 자기자신을 불러 반복하여 결과 값을 업데이트하는 것

loop문 없이 본인을 호출하여 반복문이 된다. 끝에 도달하면 return하는 값이 정해져있다.

표현법이 단순하고, 복잡한 문제를 간단하게 해결할 수 있다.

but, 이해하는게 어려울 수 있다. 재귀로 간단하게 해결할 순 있지만 쉬운건 아님!!!!

 

Base case

: Values of the input variables for which we perform no recursion calls are called base cases (there should be at least one base case).

: Every possible chain of recursive calls must eventually reach a base case.

가장 끝에 도달한 경우에 return하는 값

 

recursive calls : Each recursive call should be defined so that it makes progress towards a base case.

 

recursive call이 불리는 중에는 값을 알 수 없다, base case에 도달하면 값이 return되고 거꾸로 업데이트 된다고 생각하면 편하다.

---

 

Recur once : Linear recursion

재귀함수를 한 번 호출한다.(한 번 함수를 call 할 때)

linear recursion → time complexity가 선형 O(n)

 

ex) 팩토리얼, n 제곱 계산

 

Binary recursion

재귀 함수를 두 번 호출한다.

 

ex) 자 눈금 그리기(DrawTicks method for drawing ticks on an English ruler), 피보나치 

 

---

더 효율적으로

 

power(x, n)을 O(n)으로 수행

​

O(log n)으로 수행하도록 하는 방법

계산량이 한 번 호출할 때마다 크게 줄어든다. (탐색 범위가 절반으로)

짝수/홀수 경우를 나눈 것이므로 binary recursion은 아니다.

 

 

Fibonacci

binary recursion : O(n^2)의 시간복잡도를 가진다.

굉장히 비효율적이다. 계속해서 recursion call의 횟수가 두 배씩 증가한다.

예를 들어서 F_4로 재귀를 수행하면

 

BinaryFib(4)

F_4 = F_3 + F_2

F_3 = F_2 + F_1

F_2 = F_1 + F_0

이런 식으로 재귀를 call하게 될 것이다. 이때 재귀함수를 중복해서 불러온다는 것을 알 수 있다.

 

보다 효율적으로 만들기 위해서, return값이 Binary Recursion인 지금에서 계산한 결과값을 (i, j)의 형태로 저장해서 return하는 방식으로 바꾼다. 이전에는 이미 계산한 것도 다시 함수를 call했지만, 이젠 계산한 값을 불러오는 식으로 수정할 수 있다. 실제 구현으로 가면 배열에 저장하거나 여러가지 방법이 가능할 것이다.