재귀(Recursion)

사전적 정의의 재귀란 어떤 것을 정의할 때 자기 자신을 참조하는 것을 말하고 컴퓨터에서는 재귀 호출(recursion call)의 형태로 많이 사용된다. 

장점: 코드의 간결함

단점: 무한 재귀호출의 위험성

 

재귀적 정의의 구성

1. 기본 단계: 몇몇 초기 원소들을 기술한다.

2. 귀납적 단계: 이미 존재하는 원소들로부터 새로운 원소들을 구성하는 규칙을 제시

 

가장 많이 사용하는 코드인 factorial code이다.

def factorial(num):     if num < 1:         return 1 //기본 단계로 f(0) = 1을 기술     else:         return num * factorial(num-1) //귀납적 단계로 f(n) = n * f(n-1)의 규칙을 제시하고 있음

+ 재귀 알고리즘 예시

- 피보나치 수열, 팩토리얼

- 병합 정렬, 퀵 정렬

- 이진 컴색

- 트리 탐색

- 그래프 탐색

- 동적 계획법

- 분할 정복 알고리즘

- 하노이의 탑

- 백트래킹 알고리즘