[알고리즘] 재귀호출

재귀 호출은 함수가 자기 자신을 다시 호출하는 것을 뜻한다. 알고리즘 공부에 있어서 중요한 개념이므로 확실하게 공부해야 한다. 재귀 호출에서 중요한 것이 반드시 '종료 조건'이 있어야 한다는 것이다. 만약 종료 조건이 없으면 무한루프에 빠지기 때문이다.

 

재귀 호출의 일반적인 형태

def func(입력):
	if 입력 값이 충분히 작으면: #종료 조건
    	return 결과
    ...
    func(더 작은 입력 값)  	# 더 작은 값으로 재귀 호출
    ...
    return 결과

 

재귀 호출의 세 가지 요건

1. 함수 안에서 자기 자신을 다시 호출한다.
2. 재귀 호출할 때 인자로 주어지는 입력 크기가 작아진다.
3. 특정 종료 조건이 만족되면 재귀 호출을 종료한다. 즉, 종료 조건이 있어야 한다.

 

[예 제]

1. 1부터 n까지 더하기

def call_sum(n):
    if n <= 1:
        return n

    return n + call_sum(n-1)


print(call_sum(100))

함수 안에서 자기 자신을 계속해서 호출하는 방식으로 1부터 n까지 합을 구한다. 

 

 

2. 팩토리얼 구하기

def fact(n):
    if (n <= 1):
        return 1

    return n * fact(n-1)


print(fact(1))  # 1
print(fact(10))  # 10! = 3628800

종료 조건으로 n이 1과 같거나 작아지면 1을 리턴하게 해 마지막으로 1이 곱해지면서 결과를 리턴한다.

 

 

3. 최댓값 찾기

def find_max(nums, n):
    if n == 1:
        return nums[0]

    max_num = find_max(nums, n-1)

    if (max_num > nums[n-1]):
        return max_num
    else:
        return nums[n-1]


a = [17, 92, 18, 24, 35]
print(find_max(a, len(a)))  # 92

사실 리스트에서 최댓값, 최솟값을 구할 때 max(), min() 함수를 사용하면 쉽게 구할 수 있다.