자료구조와 알고리즘

재귀

재귀

• 어떠한 것을 정의할 때 자기자신을 참조하는 것

재귀함수

• 재귀적으로 정의된 함수

• 탈출 조건, 기저조건이 반드시 있어야함

for문 vs 재귀함수

• 재귀함수는 for문 대신이 아님

• 재귀함수로 해결하면 더 많은 메모리 공간을 차지하여 비효율적

• 재귀함수는 더 복잡한 문제를 쉽게 해결하기 위해 사용함 ex) 팩토리얼

   

재귀적으로 생각하기

1. 단순한 반복실행

   1. 재귀함수 이점이 없고 콜스택 공간을 많이 차지해 성능은 for문보다 안 좋음

2. 하위 문제의 결과를 기반으로 현재 문제를 계산 (하향식 계산)

   1. 재귀를 사용하는 이유로 재귀함수에서만 구현할 수 있음

   2. ex) 팩토리얼 return number * factorial(number - 1)

재귀 - 하노이탑

하노이탑

1. 한 번에 하나의 원반을 움직일 수 있다.

2. 가장 위에 있는 원반만 옮길 수 있다.

3. 아래에 작은 원반이 올 수 없다.

정렬 - 버블정렬

버블정렬

• 앞에 있는 숫자와 옆의 숫자를 비교해서 자리를 바꾸는 알고리즘

• 구현이 쉬우나 성능이 좋진 않음 o(n2)