재귀함수

재귀(Recursion)

함수가 자기자신을 호출하는 것.

재귀 함수는 무한 반복에 빠질 위험有. 재귀를 멈추기 위한 기본 단계가 필요함.

• 재귀 단계 : 함수가 자기 자신을 호출하는 부분.
• 기본 단계 : 함수가 자기 자신을 호출하지 않는 경우 (=재귀를 반복하다가 마지막으로 기본 단계에 도달)

def countdown(i):
	print(i)
	if(i<=1):
		return 1          #기본단계
	else:
		countdown(i-1)    #재귀단계

countdown(4)

4
3
2
1

 

재귀함수 예제 - 리스트 원소 합 구하기

반복문으로 작성된 함수를 재귀함수 형식으로 변환할 수 있다.

[반복문ver]

def sum(list):
	total = 0
	for i in list:
		total += i
	return total

my_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(sum(my_list))    #55

[재귀함수ver]

def sum(list):
	if list == []:
		return 0                        #기본단계
	else:
		return list[0] + sum(list[1:])  #재귀단계

my_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(sum(my_list))     #55

1. 리스트의 첫번째[0] 값에 그 이후 값 리스트[1:]의 총합을 더해서 리턴
2. 그 이후 값 리스트[1:]의 총합을 구하기 위해 sum()함수 재귀 => 재귀 단계
3. return list[0] + sum(list[1:])문을 타고 재귀를 반복하다가, sum(list[1:]) 호출 시 전달되는 리스트가 공란일 경우 if list == [] 조건에 걸려서 0을 리턴 (함수 실행 후 최초로 값 반환) => 기본 단계
4. 기본 단계에서 반환 받은 값은 직전 재귀에서 실행된 return list[0] + sum(list[1:]) 문에서 받아서 덧셈
5. 그렇게 덧셈해서 나온 값을 다시 직전 재귀로 반환

 

리스트 재귀함수에서 기본 단계는 보통 빈 배열이거나 원소가 하나뿐인 배열
그러므로, 기본 단계를 위해서 아래와 같은 재귀 탈출 조건을 넣어준다.

#빈배열
if list == []:
	return 0

#원소가 하나뿐인 배열
if len(list) < 2:
	return list[0]

 

재귀함수 예제 - 팩토리얼 문제

[반복문 ver]

def fact(x):
	result = x
	while(x > 1):
		x -= 1
		result *= x

	return result

print(fact(5))		#120

[재귀 ver]

def fact(x):
	if x == 1:
		return 1
	else:
		return x * fact(x-1)

print(fact(5))   #120

스택

후입선출(LIFO:Last In First Out) 방식의 자료구조.
최근에 삽입(push)된 데이터가 먼저 삭제(pop)된다.

호출 스택

여러 개의 함수를 중첩 호출하면서 함수에 사용되는 변수를 저장하는 스택.
함수가 호출될 때 스택에 push되며 함수가 return되는 순간 스택에서 pop된다.

재귀 함수는 호출 시 마다 스택 메모리가 사용되기 때문에 무한 반복에 빠지게 되면 호출 스택의 메모리를 과도하게 소비하게 된다.