재귀 (Recursion)

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

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

---

1.1 팩토리얼 함수

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

 

for num in range(10):
    print (factorial(num))
    
>>
0
1
2
6
24
120
720
5040
40320
362880

---

1.2 팩토리얼 함수 - 시간 복잡도와 공간 복잡도

factorial(n) 은 n - 1 번의 factorial() 함수를 호출해서, 곱셈을 함 

• 일종의 n-1번 반복문을 호출한 것과 동일
• factorial() 함수를 호출할 때마다, 지역변수 n 이 생성됨
• 함수는 동일하지만 함수를 호출할 때마다, 그 호출한 함수 안에서만 생성되는 n이라는 지역변수가 생성된다.

 

시간 복잡도/공간 복잡도는 O(n-1) 이므로 결국, 둘 다 O(n)

---

1.3 재귀 호출의 2가지 일반적인 형태

 

(1) 입력 값이 일정 값 이상일 때

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

 

(2) 입력값이 일정 값 미만일 때

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

 

 

일반적인 형태2의 팩토리얼 함수

def factorial(n):
    if n < 2:
        return n
   
    return n * factorial(n-1)

 

---

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

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

 

 

 

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

 

---

2. 재귀함수 프로그래밍 연습

---

2.1 1부터 n까지 곱하는 함수 만들기

def multiple(n):
    return_value = 1
    for i in range(1, n+1):
        return_value *= i
    return return_value

 

재귀함수로 만들어 보기

def multiple_re(n):
    return_value = 1
    if n > 1:
        return n * mutiple_re(n-1)
    else :
        return 1

def mutiple_re2(n):
    return_value = 1
    if n <= 1:
        return return_value
    else:
        return n * multiple_re2(n-1)

---

2.2 숫자가 들어 있는 리스트가 주어졌을 때, 리스트의 합을 리턴하는 함수 만들기

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

 

import random 
data = random.sample(range(100), 10)
data

>> [72, 50, 8, 38, 77, 32, 90, 48, 74, 79]

함수의 첫 호출에서 data[0] = 72 이고,

그 다음 호출에서는 data[0] = 50,

그 다음 호출에서는 data[0] = 8,

이렇게 가다가 마지막에 data[0] = 79 만 남게 된다.

 

79, 74, 48, 90 ... 이런 순으로 리턴 받으면서 값을 더하게 된다.

 

---

2.3 회문을 판별할 수 있는 함수를 리스트 슬라이싱을 활용해서 만드세요

회문(palindrome)은 순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장을 의미함

motor는 회문이 아니다.

 

참고 - 리스트 슬라이싱

string = 'Dave'

string[-1] # -1은 맨 뒤를 지칭한다.
>> e 
string[0] 
>> D
string[1:-1] # 뒤에있는 인덱스의 앞까지만 
>> av
string[:-1] 
>> Dav

 

회문 판별함수 만들기

def palindrome(string):
    if len(string) <= 1: # 문자가 하나거나 0개라면 다 맞은것이기 때문에 회문이다.
        return True
    
    if string[0] == string[-1]: # 맨앞 문자, 맨뒤 문자 비교
        return palindrome(string[1:-1]) # 같다면 그다음 문자
    else:
        return False

 

---

2.4 연습

1, 정수 n에 대해
2. n이 홀수이면 3 × n + 1 을 하고,
3. n이 짝수이면 n 을 2로 나눕니다.
4. 이렇게 계속 진행해서 n 이 결국 1이 될 때까지 2와 3의 과정을 반복합니다.

 

3을 넣으면

 

3

10

5

16

8

4

2

1

def func(n):
    print(n)
    if n == 1:
        return n
    if n%2 == 1:
        return func(3*n + 1)
    else:
        return func(int(n/2)) # int를 안넣으면 부동소수점이 출력된다.

---

2.5 연습 (ACM-ICPC)

정수 4를 1, 2, 3의 조합으로 나타내는 방법은 다음과 같이 총 7가지가 있음

1+1+1+1

1+1+2

1+2+1

2+1+1

2+2

1+3

3+1

 

정수 n이 입력으로 주어졌을 때, n을 1, 2, 3의 합으로 나타낼 수 있는 방법의 수를 구하시오.

 

힌트: 정수 n을 만들 수 있는 경우의 수를 리턴하는 함수를 f(n) 이라고 하면,
f(n)은 f(n-1) + f(n-2) + f(n-3) 과 동일하다는 패턴 찾기

 

def func(data):
    if data == 1:
        return 1
    elif data == 2:
        return 2
    elif data == 3:
        return 4
    
    return func(data -1) + func(data - 2) + func(data - 3)