1. 재귀 용법 (recursive call, 재귀 호출)
- 함수 안에서 동일한 함수를 호출하는 형태
- 여러 알고리즘 작성시 사용되므로, 익숙해져야 함
- 코드분석
def factorial(num):
if num > 1:
return num * factorial(num - 1)
else:
return num
for num in range(10):
print (factorial(num))2. 재귀 호출은 스택의 전형적인 예
- 함수는 내부적오르 스택처럼 관리된다.
3. 재귀 호출의 일반적인 형태들
# 일반적인 형태1
def function(입력):
if 입력 > 일정값: # 입력이 일정 값 이상이면
return function(입력 - 1) # 입력보다 작은 값
else:
return 일정값, 입력값, 또는 특정값 # 재귀 호출 종료
# 일반적인 형태2
def function(입력):
if 입력 <= 일정값: # 입력이 일정 값보다 작으면
return 일정값, 입력값, 또는 특정값 # 재귀 호출 종료
function(입력보다 작은 값)
return 결과값
# 테스트
def factorial(num):
if num <= 1:
return num
return num * factorial(num - 1)
for num in range(10):
print (factorial(num))
0
1
2
6
24
120
720
5040
40320
3628804. 시간 복잡도와 공간 복잡도
- factorial(n) 은 n - 1 번의 factorial() 함수를 호출해서, 곱셈을 함
- 일종의 n-1번 반복문을 호출한 것과 동일
- factorial() 함수를 호출할 때마다, 지역변수 n 이 생성됨
- 시간 복잡도 / 공간 복잡도는 O(n-1) 이므로 결국, 둘 다 O(n)
5. 재귀 용법을 활용한 프로그래밍 연습
5-1. 1부터 n까지의 곱을 출력하는 재귀 함수
- JS
function multiple(n) { if (n <= 1) { return n; } let result = 1; for (let i = 1; i <= n; i++) { result *= i; } return result; } let r1 = multiple(5); console.log(r1); function rMultiple(n) { if (n <= 1) { return n; } return n * rMultiple(n - 1); } let r2 = multiple(5); console.log(r2); - Python
# for문 사용하여 구현 def multiple(n): result = 1 for i in range(1, n+1): result = result * i return result multiple(4) # 재귀함수 사용하여 구현 def multiple(n): if n <= 1: return n return n * multiple(n-1) multiple(4)
5-2. 숫자가 들어 있는 리스트가 주어졌을 때, 리스트의 합을 리턴하는 재귀 함수
- JS
function totalArray(arr) { let result = 0; for (let i = 0; i < arr.length; i++) { result += arr[i]; } return result; } let r1 = totalArray([1, 2, 3, 4, 5, 6]); console.log(r1); function rTotalArray(arr, i = 0) { let result = 0; if (i == 0) { return arr[0]; } return arr[i] + rTotalArray(arr, i - 1); } let r2 = rTotalArray([1, 2, 3, 4, 5, 6], 5); console.log(r2); function sumList(data) { let result = 0; if (data.length <= 1) { return data[0]; } else { return data[0] + sumList(data.slice(1)); } } let r3 = sumList([1, 2, 3, 4, 5, 6]); console.log(r3); - Python
def sumList(data): result = 0 if len(data) <= 1: return data[0] else: return data[0] + sumList(data[1:]) import random data = random.sample(range(100), 3) print(data) sumList(data) [84, 7, 68] 159
5-3. 회문을 판별할 수 있는 재귀 함수
- 회문(palindrome)은 순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장을 의미함
- JS
function palindrome1(arr) { if (arr.length === 1) { return true; } if (arr[0] === arr[arr.length - 1]) { return palindrome1(arr.slice(1, -1)); } else { return false; } } let r1 = palindrome1("hello"); console.log(r1); let r2 = palindrome1("hoasdflfdsaoh"); console.log(r2); - Python
-
리스트 슬라이싱을 활용
``` string = 'Dave' string[-1] --> e string[0] --> D string[1:-1] --> av string[:-1] --> Dav ```def palindrome(textList): if len(textList) <= 1: return True if textList[0] == textList[-1]: return palindrome(textList[1:-1]) else: return False textList = ['m', 'o', 't', 'o', 'r'] palindrome(textList) # False textList = ['m', 'i', 'o', 't', 'o', 'i', 'm'] palindrome(textList) # True textList = ['m', 'i', 'o', 'o', 'i', 'm'] palindrome(textList) # True
-
5-4. 정수 n을 입력받아, 아래 알고리즘에 의해 1이 되는 과정을 모두 출력하는 함수를 작성
- 정수 n에 대해
- n이 홀수이면 3 X n + 1 을 하고,
- n이 짝수이면 n 을 2로 나눕니다.
- 이렇게 계속 진행해서 n 이 결국 1이 될 때까지 2와 3의 과정을 반복합니다.
- JS
function func(n) { console.log(n); if (n <= 1) { return; } if (n % 2 === 0) { return func(n / 2); } else { return func(3 * n + 1); } } let r1 = func(100); console.log(r1); - Python
# 3입력시 결과 3 10 5 16 8 4 2 1def func(n): print(n) if n <= 1: return n if n % 2 == 0: return func(int(n/2)) else: return func(3*n+1) func(3)
5-5. 정수 n이 입력으로 주어졌을 때, n을 1, 2, 3의 합으로 나타낼 수 있는 방법의 수를 구하는 함수
패턴 분석
- 1 입력 시: 1 리턴
- 2 입력 시: 2 리턴
- 3 입력 시: 4 리턴
- 4 입력 시: 이전 3개의 개수의 합, 1+2+4=7 리턴
- 5 입력 시: 이전 3개의 개수의 합, 2+4+7=13 리턴
- 6 입력 시: 이전 3개의 개수의 합, 4+7+13=24 리턴
- ...
패턴 정리
정리해보면 f(n)은 1, 2, 3이 입력되었을때를 제외하고 4 이상일 경우 다음의 패턴을 갖는다.
패턴: f(n-1) + f(n-2) + f(n-3)
코드 구현
- JS
function func(n) { if (n <= 1) { return 1; } if (n == 2) { return 2; } if (n == 3) { return 4; } return func(n - 1) + func(n - 2) + func(n - 3); } let r1 = func(1); console.log(r1); r1 = func(2); console.log(r1); r1 = func(3); console.log(r1); r1 = func(5); console.log(r1); r1 = func(6); console.log(r1); r1 = func(7); console.log(r1); r1 = func(8); console.log(r1); r1 = func(10); console.log(r1); - Python
def func(n): if n == 1: return n elif n == 2: return 2 elif n == 3: return 4 return func(n-1) + func(n-2) + func(n-3) func(5) 13 func(6) 24 func(7) 44 func(8) 71 func(10) 274
Move fast & break things