잔재미코딩
블로그 자료모음 기업교육

재귀 용법 (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 맞다!
    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 맞다!

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

본 자료와 같이 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))

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 일정값 # 재귀 호출 종료
본 자료와 같이 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))

0
1
2
6
24
120
720
5040
40320
362880

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

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

본 자료와 같이 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))

0
1
2
6
24
120
720
5040
40320
362880
본 자료와 같이 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]:
382
In [92]:
data_list
Out[92]:
[44, 71, 3, 67, 36, 64, 22, 45, 5, 25]
본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다
체계적으로 전문가 레벨까지 익힐 수 있도록 온라인 강의 로드맵을 제공합니다
데이터 분석/과학 로드맵
데이터 분석/과학 로드맵
데이터 분석가와 데이터 과학자 직군의 기본기를 차근차근 쌓을 수 있도록 꾸몄습니다
자세히 알아보기 모든 강좌 보기
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
본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다
체계적으로 전문가 레벨까지 익힐 수 있도록 온라인 강의 로드맵을 제공합니다
웹/앱서비스 풀스택 로드맵
웹/앱서비스 풀스택 로드맵
웹/앱 백엔드와 프론트엔드 기술과 서버/배포 기술을 포함하여 풀스택 기본기를 차근차근 쌓을 수 있도록 꾸몄습니다
자세히 알아보기 모든 강좌 보기

프로그래밍 연습
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)
본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다
체계적으로 전문가 레벨까지 익힐 수 있도록 온라인 강의 로드맵을 제공합니다
데이터 분석/과학 로드맵
데이터 분석/과학 로드맵
데이터 분석가와 데이터 과학자 직군의 기본기를 차근차근 쌓을 수 있도록 꾸몄습니다
자세히 알아보기 모든 강좌 보기
In [ ]:
합리적인 분들과 확연히 다른 좋은 IT 강의를 만들 수 있는 선순환 시스템을 지향합니다
컨택: dream@fun-coding.org
Copyright 2022 © (주)노이먼스 All rights reserved.