잔재미코딩

재귀 용법 (Recursive Call)

처음하는 파이썬 머신러닝 부트캠프

혹시 본 자료가 도움이 되셨다면, 이런 식으로 잘 정리된 코드/자료로 만든 제 강의 한번 봐주실래요?

처음하는 파이썬 머신러닝 부트캠프

쉽게! 캐글 문제와 함께 분류,회귀,군집화 익히기

자세히 알아보기 모든 강좌 보기

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

고급 정렬 알고리즘엥서 재귀 용법을 사용하므로, 고급 정렬 알고리즘을 익히기 전에 재귀 용법을 먼저 익히기로 합니다.

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

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

2. 재귀 용법 이해

  • 예제를 풀어보며, 재귀 용법을 이해해보기

예제

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

예제 - 분석하기

  • 간단한 경우부터 생각해보기
    • 2! = 1 X 2
    • 3! = 1 X 2 X 3
    • 4! = 1 X 2 X 3 X 4
  • 규칙이 보임: n! = n X (n - 1)!
    1. 함수를 하나 만든다.
    2. 함수(n) 은 n > 1 이면 return n X 함수(n - 1)
    3. 함수(n) 은 n = 1 이면 return n
  • 검증 (코드로 검증하지 않고, 직접 간단한 경우부터 대입해서 검증해야 함)
    1. 먼저 2! 부터
      • 함수(2) 이면, 2 > 1 이므로 2 X 함수(1)
      • 함수(1) 은 1 이므로, return 2 X 1 = 2 맞다!
    2. 먼저 3! 부터
      • 함수(3) 이면, 3 > 1 이므로 3 X 함수(2)
      • 함수(2) 는 결국 1번에 의해 2! 이므로, return 2 X 1 = 2
      • 3 X 함수(2) = 3 X 2 = 3 X 2 X 1 = 6 맞다!
    3. 먼저 4! 부터
      • 함수(4) 이면, 4 > 1 이므로 4 X 함수(3)
      • 함수(3) 은 결국 2번에 의해 3 X 2 X 1 = 6
      • 4 X 함수(3) = 4 X 6 = 24 맞다!

예제 - 코드 레벨로 적어보기

처음하는 파이썬 머신러닝 부트캠프

혹시 본 자료가 도움이 되셨다면, 이런 식으로 잘 정리된 코드/자료로 만든 제 강의 한번 봐주실래요?

처음하는 파이썬 머신러닝 부트캠프

쉽게! 캐글 문제와 함께 분류,회귀,군집화 익히기

자세히 알아보기 모든 강좌 보기
In [1]:
def factorial(num):
    if num > 1:
        return num * factorial(num - 1)
    else:
        return num
In [2]:
# 코드로 검증 
for num in range(10):
    print (factorial(num))

0
1
2
6
24
120
720
5040
40320
362880

예제 - 시간 복잡도와 공간 복잡도

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

    • 일종의 n-1번 반복문을 호출한 것과 동일
    • factorial() 함수를 호출할 때마다, 지역변수 n 이 생성됨

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

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

In [ ]:
# 일반적인 형태1
def function(입력):
    if 입력 > 일정값: # 입력이 일정 값 이상이면
        return function(입력 - 1) # 입력보다 작은 값
    else:
        return 일정값 # 재귀 호출 종료
In [ ]:
# 일반적인 형태2
def function(입력):
    if 입력 <= 일정값:              # 입력이 일정 값보다 작으면
        return 결과값              # 재귀 호출 종료
    function(입력보다 작은 값)
    return 결과값
In [71]:
# 일반적인 형태2 로 작성한 팩토리얼
def factorial(num):
    if num <= 1:
        return num
    return_value = num * factorial(num - 1)       # return num * factorial(num - 1) 로 작성하는 것도 좋음
    return return_value
처음하는 파이썬 머신러닝 부트캠프

혹시 본 자료가 도움이 되셨다면, 이런 식으로 잘 정리된 코드/자료로 만든 제 강의 한번 봐주실래요?

처음하는 파이썬 머신러닝 부트캠프

쉽게! 캐글 문제와 함께 분류,회귀,군집화 익히기

자세히 알아보기 모든 강좌 보기
In [72]:
# 코드로 검증 
for num in range(10):
    print (factorial(num))

0
1
2
6
24
120
720
5040
40320
362880

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

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

  • 재귀 호출이 이해가 가지 않는다면? - 코드분석

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

4. 재귀 용법을 활용한 프로그래밍 연습

프로그래밍 연습
다음 함수를 재귀 함수를 활용해서 완성해서 1부터 num까지의 곱이 출력되게 만드세요 
def muliple(data):
    if data <= 1:
        return data

    return -------------------------

multiple(10)
In [82]:
def multiple(data):
    return_value = 1
    for index in range(1, data+1):
        return_value = return_value * index
    return return_value
처음하는 파이썬 머신러닝 부트캠프

혹시 본 자료가 도움이 되셨다면, 이런 식으로 잘 정리된 코드/자료로 만든 제 강의 한번 봐주실래요?

처음하는 파이썬 머신러닝 부트캠프

쉽게! 캐글 문제와 함께 분류,회귀,군집화 익히기

자세히 알아보기 모든 강좌 보기
In [7]:
def multiple(data):
    if data <= 1:
        return data

    return data * multiple(data - 1)

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

0
1
2
6
24
120
720
5040
40320
362880

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

참고: 임의 값으로 리스트 만들기 random.sample(0 ~ 99까지 중에서, 임의로 10개를 만들어서 10개 값을 가지는 리스트 변수 만들기
import random 
data = random.sample(range(100), 10)
In [83]:
import random 
data = random.sample(range(100), 10)
data
Out[83]:
[50, 76, 39, 55, 6, 20, 37, 17, 5, 23]

프로그래밍 연습
숫자가 들어 있는 리스트가 주어졌을 때, 리스트의 합을 리턴하는 함수를 만드세요 (재귀함수를 써보세요) 

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

    return --------------------------------

import random 
data = random.sample(range(100), 10)
print (sum_list(data))
In [89]:
def sum_list(data):
    return_value = 0
    for item in data:
        return_value = return_value + item
    return return_value

data_list = random.sample(range(100), 10)
sum_list(data_list)
Out[89]:
382
In [92]:
data_list
Out[92]:
[44, 71, 3, 67, 36, 64, 22, 45, 5, 25]
In [94]:
data_list[-1]
Out[94]:
25
처음하는 파이썬 머신러닝 부트캠프

혹시 본 자료가 도움이 되셨다면, 이런 식으로 잘 정리된 코드/자료로 만든 제 강의 한번 봐주실래요?

처음하는 파이썬 머신러닝 부트캠프

쉽게! 캐글 문제와 함께 분류,회귀,군집화 익히기

자세히 알아보기 모든 강좌 보기
In [91]:
def sum_list(data):
    # print(data)
    if len(data) == 1:
        return data[0]

    return data[0] + sum_list(data[1:])

sum_list(data_list)

[44, 71, 3, 67, 36, 64, 22, 45, 5, 25]
[71, 3, 67, 36, 64, 22, 45, 5, 25]
[3, 67, 36, 64, 22, 45, 5, 25]
[67, 36, 64, 22, 45, 5, 25]
[36, 64, 22, 45, 5, 25]
[64, 22, 45, 5, 25]
[22, 45, 5, 25]
[45, 5, 25]
[5, 25]
[25]
Out[91]:
382

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

참고 - 리스트 슬라이싱
string = 'Dave' 
string[-1] --> e
string[0] --> D
string[1:-1] --> av
string[:-1] --> Dav
프로그래밍 연습
회문(palindrome)은 순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장을 의미함
회문을 판별할 수 있는 함수를 재귀함수를 활용해서 만들어봅니다.
In [6]:
def recursive(string):
    if len(string) <= 1:
        return True
    
    if string[0] == string[-1]:
        return recursive(string[1:-1])
    else:
        return False

print (recursive('ruur'))

True

프로그래밍 연습
1, 정수 n에 대해

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

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

3
10
5
16
8
4
2
1
이 됩니다.

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

In [37]:
def func(data):
    print (data)
    if data == 1:
        return

    if data % 2 == 0:
        return func(int(data / 2))
    else:
        return func(3 * data + 1)
프로그래밍 연습
문제: 정수 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) 과 동일하다는 패턴 찾기
출처: ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Taejon 2001
처음하는 파이썬 머신러닝 부트캠프

혹시 본 자료가 도움이 되셨다면, 이런 식으로 잘 정리된 코드/자료로 만든 제 강의 한번 봐주실래요?

처음하는 파이썬 머신러닝 부트캠프

쉽게! 캐글 문제와 함께 분류,회귀,군집화 익히기

자세히 알아보기 모든 강좌 보기

문제 분석을 연습장에 작성해 본 예

In [104]:
def f(data):
    if data < 0:
        return 0
    if data == 0:
        return 1
    elif data == 1:
        return 1
    elif data == 2:
        return 2
    elif data == 3:
        return 4
    
    return f(data - 1) + f(data - 2) + f(data - 3)
In [ ]:

선택 정렬 (selection sort) 동적 계획법과 분할 정복