재귀 함수란, 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 주어진 문제를 푸는 방법이다.

재귀함수는 매 호출시마다 입력값이 변한다. 입력값의 변화가 없는 호출은 무한히 반복된다.

입력값의 변화가 없거나 입력값의 변화가 특정 패턴을 반복하게 되면 그 재귀함수는 영원히 반복되다가 콜스택 초과로 종료된다.

따라서 재귀함수 설계 시에는 입력값이 종료 조건으로 수렴하는지를 꼭 검증해야 한다.

재귀 함수의 구조는 크게 2가지로 나눌 수 있다.

종료 조건 (base case)

재귀 함수가 무한 호출에 빠지지 않게 해주는 조건을 명시하는 것이다.

이는 곧 이미 문제가 충분히 작아서, 더 작은 부분 문제로 나누지 않고도 바로 답을 알 수 있는 경우를 뜻한다.

재귀 조건 (recursive case)

종료 조건을 만족하지 못한 나머지 경우를 뜻한다.

즉, 현 문제가 너무 커서, 같은 형태의 더 작은 부분 문제를 재귀적으로 푸는 경우이다.

1부터 N까지의 합 계산

1. 반복문 활용

def sum(n):
    s = 0
    for i in range(1, n + 1):
        s += i
    return s

• 수행 시간

2. 재귀적 방법 1

• 논리

def sum(n):
	if n <= 1: return n
	return n + sum(n-1)

• 수행 시간