[알고리즘] 재귀 용법 (recursive call)

재귀 용법(recursive call, 재귀 호출)

  - 함수 안에서 동일한 함수를 호출하는 형태

  - 여러 알고리즘 작성 시 사용되므로, 익숙해져야 한다.

 

예제

  - 팩토리얼 구하는 알고리즘 작성하기

  - 2! = 1 * 2

     3! = 1 * 2 * 3

     4! = 1 * 2 * 3 * 4

     규칙 : n! = n * (n-1)!

def factorial(num):
	if num > 1:
		return num * factorial(num - 1)
	else:
		return num	# 재귀 함수 종료
        
print(factorial(10))	# 362880

  - factorial() 함수를 호출할 때마다, 지역변수 n 이 생성됨

  - 시간 복잡도 / 공간 복잡도는 O(n)

  - 함수는 내부적으로 스택처럼 관리된다.

 

  - 리스트 총 합 알고리즘 작성하기

def sum_list(data):
	print(data)
	if len(data) == 1:
		return data[0]
	return data[0] + sum_list(data[1:])

data_list = [1, 2, 3, 4, 5]

print(sum_list(data_list))

#  [1, 2, 3, 4, 5]
#  [2, 3, 4, 5]
#  [3, 4, 5]
#  [4, 5]
#  [5]
#  15