재귀함수(recursive functions)란?

하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것

생각보다 많은 문제가 재귀적으로(recursively) 해결 가능

예1) 이진 트리 - 왼쪽 서브트리의 원소는 모두 작거나 같을 것, 오른쪽 서브트리의 원소들은 모두 클 것 -> 이 원칙을 모든 노드에 적용

• 루트 노드부터 탐색하려는 노드까지 재귀적으로 찾아가게 됨

예2) 1부터 n까지 모든 자연수의 합을 구하기

defsum(n):
if n <= 1:
return n
else:
return n + sum(n-1)
a = int(input("Number: "))
print(sum(a))

재귀 호출의 종결 조건

알고리즘은 유한한 시간내에 답을 내야하는데 종결 조건이 반드시 필요하다.

재귀 알고리즘의 효율

모든 재귀 알고리즘은 그와 대칭하는 반복적 알고리즘(while, for)을 갖게 된다.

• Recursive version VS Iterative version
• 시간 복잡도: O(n) VS O(n)
• 효율성은 재귀 알고리즘이 함수 호출을 반복하기 때문에 반복적인 알고리즘보다 비효율적일 수 있다.

defsum(n):
return n * (n + 1) // 2

이 경우는 극단적으로 O(1)의 시간 복잡도를 가지는 1부터 n까지의 자연수의 합을 구하는 코드다.

추가 예제