[자료구조 및 알고리즘] 2주차 - 재귀와 귀납적 사고(1)

학습 목표

▶ 재귀의 뜻을 이해한다.

▶ 재귀가 사용되는 문제의 예시들을 학습하여 재귀의 원리를 이해한다.

▶ 재귀와 수학적 귀납법 간의 밀접한 관계를 이해한다.

 

# 재귀는 자주 등장하는 주제, 자료구조와 알고리즘을 공부하면서 반드시 알고 있어야 하는 주제

 

재귀(recursion)란?

• 내 안의 나를 찾는 것
• 성격은 같고 크기만 작은 나를 찾아 큰 나와 작은 나가 연결된 관계를 드러내는 것
• 재귀 함수(recusive function), 재귀 호출(recursive call)
• 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법
• 정의 자체가 순환적으로 되어 있는 경우에 적합한 방법

재귀 알고리즘

• 자신과 성격은 똑같지만 크기만 작은 알고리즘(들)을 호출하는 알고리즘
• 복잡한 문제도 간명하게 볼 수 있게 한다
  • ex) 탐색, 정렬, 수열,....
• 잘 쓰면 보약
  • ex) 정렬, 탐색,....
• 잘못 쓰면 독약
  • 피보나치 수 구하기, 최적 행렬곱 경로,....
• 재귀 알고리즘의 구조
  • 재귀를 멈추는 부분 (멈추는 부분이 없다면, 시스템 오류가 발생할 때 까지 무한정 호출)
  • 재귀 호출을 하는 부분

순환(재귀) ↔ 반복

• 대부분의 순환은 반복으로 바꾸어 작성할 수 있다.
• ex) 4! = 1*2*3*4
• 순환과 반복 알고리즘의 시간 복잡도가 동일할 경우 무엇이 더 효율적인가?
  • 메모리 측면에서 반복이 더 효율적임