재귀 용법 (Recursive Call)

이해하기 쉽고, 장황하지 않은 자료를 기반으로 강의를 진행합니다.

잔재미코딩 소식 공유

좀더 제약없이, IT 컨텐츠를 공유하고자, 자체 온라인 강의 사이트와 유투브 채널을 오픈하였습니다
응원해주시면, 곧 좋은 컨텐츠를 만들어서 공유하겠습니다

● 직운영 온라인 강의 서비스 오픈

● 잔재미코딩 유투브 오픈 [구독해보기]

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 맞다!
1. 먼저 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 맞다!
1. 먼저 4! 부터
- 함수(4) 이면, 4 > 1 이므로 4 X 함수(3)
  - 함수(3) 은 결국 2번에 의해 3 X 2 X 1 = 6
  - 4 X 함수(3) = 4 X 6 = 24 맞다!

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

본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다

체계적으로 전문가 레벨까지 익힐 수 있도록 온라인 강의 로드맵을 제공합니다

데이터 분석/과학 로드맵

데이터 분석가와 데이터 과학자 직군의 기본기를 차근차근 쌓을 수 있도록 꾸몄습니다

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

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))

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

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 일정값 # 재귀 호출 종료

본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다

가장 빠르게 풀스택 개발자가 될 수 있도록, 최적화된 로드맵을 제공합니다

웹/앱서비스 풀스택 로드맵

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

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))

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

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

No description has been provided for this image

본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다

체계적으로 전문가 레벨까지 익힐 수 있도록 온라인 강의 로드맵을 제공합니다

데이터 분석/과학 로드맵

데이터 분석가와 데이터 과학자 직군의 기본기를 차근차근 쌓을 수 있도록 꾸몄습니다

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

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

참고: 파이썬에서 재귀 함수는 깊이가(한번에 호출되는...) 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))

본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다

가장 빠르게 풀스택 개발자가 될 수 있도록, 최적화된 로드맵을 제공합니다

웹/앱서비스 풀스택 로드맵

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

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

참고: 임의 값으로 리스트 만들기 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]:

In [92]:

data_list

Out[92]:

[44, 71, 3, 67, 36, 64, 22, 45, 5, 25]

본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다

체계적으로 전문가 레벨까지 익힐 수 있도록 온라인 강의 로드맵을 제공합니다

데이터 분석/과학 로드맵

데이터 분석가와 데이터 과학자 직군의 기본기를 차근차근 쌓을 수 있도록 꾸몄습니다

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

In [94]:

data_list[-1]

Out[94]:

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]:

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

참고 - 리스트 슬라이싱
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

본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다

가장 빠르게 풀스택 개발자가 될 수 있도록, 최적화된 로드맵을 제공합니다

웹/앱서비스 풀스택 로드맵

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

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

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

이 됩니다.

이렇게 정수 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 [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의 합으로 나타낼 수 있는 방법의 수를 구하시오

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

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)