[Algorithm][Python] 재귀호출 (recursive call)

재귀호출 (recursive call)

1. 재귀용법

• 함수 안에서 동일한 함수를 호출하는 형태
• 여러 알고리즘 작성시 사용되므로 익숙해져야 함.

2. 재귀 용법 이해

예제

• 팩토리얼을 구하는 알고리즘을 Recursive Call 을 활용해서 알고리즘 작성하기

팩토리얼의 경우, n부터 1까지의 곱셈이라고 볼 수 있다. 로직은 알고있다. 예전 수학을 배울 때 다음과 같은 방정식을 세울 수 있었다.

f(n) = f(n-1) x n

결국 함수 안에서 자기자신을 부르는 재귀함수라고 볼 수 있겠다.

파이썬으로는 이를 어떻게 적을까? 코드레벨로 작성해보자.

def factorial(num):
	if num > 1:
		return num * factorial(num -1)
	else:
		return num

for num in range(10):
	print(factorial(num))

## 0부터 9까지의 factorial 이 print 됨.

시간 복잡도와 공간 복잡도

• factorial(n) 은 n-1 번의 factorial() 함수를 호출해서 , 곱셈을 함.
  • 일종의 n-1 번 반복문을 호출한 것과 동일
  • factorial() 함수를 호출할 때마다 지역변수 n 이 생성됨.
• 시간 복잡도 / 공간 복잡도는 O(n-1) 이므로 결국 둘다 O(n)

피보나치 수열이랑 헷갈렸다… 피보나치의 경우 함수 하나에 2개가 recursive call 이 발생해서, O(n^2^) 이 되겠다.

3. 재귀 호출의 일반적인 형태

# 일반적인 형태 1
def function(입력):
	if 입력 > 일정값: # 입력이 일정 값 이상이면
		return function(입력 -1) # 입력보다 작은 값
	else:
		return 일정값, 입력값, 또는 특정값 # 재귀 호출 종료

# 일반적인 형태2
def function(입력):
	if 입력 <= 일정값: # 입력이 일정 값보다 작으면
		return 일정값, 입력값, 또는 특정값 # 재귀호출 종료
	function(입력보다 작은 값)
	return 결과값

아까 팩토리얼과 비교해보자. 이번에는 일반적인 형태 2로 해볼거다.

def factorial(num):
	if num <= 1:
		return num

	return num * factorial(num -1)

이렇게 하면 f(n) = f(n-1) _ n = n _ (n-1) * f(n-2) … 처럼 함수가 실행된다.

재귀 호출은 스택의 전형적인 예

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

참고: 파이썬에서 재귀 함수는 깊이가(한번에 호출되는) 1000회 이하가 되어야 함

4. 연습해보자… 내가 직접 코드 짜보기. 결국 재귀함수는 위의 두가지경우로 되겠지..?

프로그래밍 연습
재귀 함수를 활용해서 완성해서 1부터 num까지의 곱이 출력되게 만들어 보자.

재귀 함수

def multiple(num):
	if num <= 1:
		return num
	return num * multiple(num - 1)

일반 인덱스로 구현하기

def multiple(num):
	answer = 1
	for index in range(1, num+1):
		answer = answer * index
	return answer

프로그래밍 연습
숫자가 들어 있는 리스트가 주어졌을 때, 리스트의 합을 리턴하는 함수를 만들어 보자.

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

프로그래밍 연습
회문(palindrome)은 순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장을 의미함
회문을 판별할 수 있는 함수를 리스트 슬라이싱을 활용해서 만들어 보자.

참고 - 리스트 슬라이싱
string = 'Dave'
string[-1] --> e
string[0] --> D
string[1:-1] --> av
string[:-1] --> Dav

def palindrome(string):
	if len(string) == 1:
		return True
	if string[-1] == string[0]:
		return palindrome(string[1:-1])
	else:
		return false

< class=”alert alert-block alert-warning”> 프로그래밍 연습
1, 정수 n에 대해
2. n이 홀수이면 3 X n + 1 을 하고,
3. n이 짝수이면 n 을 2로 나눈다.
4. 이렇게 계속 진행해서 n 이 결국 1이 될 때까지 2와 3의 과정을 반복한다.

예를 들어 n에 3을 넣으면,

3
10
5
16
8
4
2
1

이 된다.

이렇게 정수 n을 입력받아, 위 알고리즘에 의해 1이 되는 과정을 모두 출력하는 함수를 작성해보자.

def func(n):
    print(n)
	if n == 1:
		return n
	if n % 2 == 1:
		return func((3*n +1))
	if n % 2 == 0:
		return func(int(n/2))