[자료구조 · 알고리즘] 재귀 알고리즘 (Recursive Algorithms)

어서와! 자료구조와 알고리즘은 처음이지? 강의 수강 후 내용을 정리한 글입니다.

 

 

재귀 함수 (recursive functions)

 

재귀 함수란 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것을 의미한다.

같은 알고리즘을 반복적으로 적용하여 풀어낸다.

 

구글에 Recursive를 검색하면 '이것을 찾으셨나요?'라며 또다시 나온다.

이 역시 재귀를 표현한 구글의 유머 감각이다.

(방심하고 봤다가 빵 터짐..)

 

• 종결 조건 (trivial case)

재귀 함수를 사용할 때에는 알고리즘의 종결 조건이 필요하다.

조건이 없다면 계속해서 무한히 반복하기 때문이다.

 

def sum(n):
	if n..:
    	...
    else:
    	...sum(..)..

 

• 예제 - n! (팩토리얼)

def what(n):
    if n <= 1:
        return 1
    else:
        return n * what(n-1)

 

what이라는 함수는 n!을 표현한 함수이다.

팩토리얼 정의 자체가 재귀적이다.

3! = 3 * 2 * 1 이므로, 값을 하나씩 낮춰가며 곱한다. 따라서 곱하는 부분은 갖기에 재귀 함수로 표현할 수 있다.

 

 

물론 재귀 알고리즘은 일반 반복문에 비해 효율성이 떨어진다는 단점이 있다.

피보나치 수열의 경우에도 반복문의 시간이 더 짧다.

하지만 유용성이 있다는 장점이 있기에 경우에 맞게 잘 활용하면 될 것 같다.