[Python Algorithm] 재귀용법(Recursive Call, 재귀호출)

재귀용법(Recursive call, 재귀호출) 이란?

  - 함수 안에서 동일한 함수를 호출하는 형태

 

 

 

문장으로 이해하기 어려우니 예제를 통해 재귀용법이 무엇인지 알아보자.

예제 1]  팩토리얼을 구하는 알고리즘을 Recursive Call 을 활용하여 작성하기.

 1. 분석

      팩토리얼이란? n! = n x (n-1)! 의 형태를 띄는 것.

      4! = 4 x 3! 

      4! = 4 x 3 x 2!

      4! = 4 x 3 x 2 x 1

 

 2.  코드로 적어보기

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

n = 1 일때는 1밖에 없음으로 자기 자신을 리턴하면 됨.

n > 1 일때는 팩토리얼의 규칙인 n x 함수(n-1)을 하면 됨.

이때, factorial 변수 내부에 factorial 변수가 또 사용 되기 때문에 재귀용법이 됨.

 

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

9까지의 팩토리얼 값을 구해봄.

[OUT] : 0 1 2 6 24 120 720 5040 40320 362880

 

 

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

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

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

일반적인 형태는 다음과 같으며, 위의 팩토리얼 예제와 비교하여 보면 이해하기 쉽다.

입력값에 num을 일정값에 1을 넣어보면서 비교해보자.

 

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

이 형태는 일반적인 형태1의 if문 순서만 바뀐 것이다.

입력된 값이 일정값 보다 작거나 같으면 본인을 리턴하고,

입력된 값이 일정값 보다 크면 결과값을 리턴한다.

 

def factorial(num):
    if num <= 1:
        return num
    
    return num * factorial(num - 1)

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

[OUT] : 0 1 2 6 24 120 720 5040 40320 362880

앞과 동일한 결과가 출력된다.

 

 

4. 재귀호출과 스택

[Image 1 - Recursive Call and Stack]

재귀 함수는 스택의 전형적인 예시이다. 

위의 이미지 처럼 함수를 한번 돌 때마다 그 값이 스택형태로 하나씩 쌓이고,

출력되면서 결과값을 도출한다.

참고로 파이썬에서는 재귀함수의 깊이를 1000이하로 제한하고 있다.

 

예제 2]  Recursive Call 을 활용하여 1부터 num까지의 곱이 출력되게 만들기.

def multiple(num):
    return_value = 1
    for index in range(1, num + 1): #num까지의 곱이니까 num+1
        return_value = return_value * index
    return return_value

1. 1부터 num까지의 곱을 출력해야 하므로 return_value를 1로 먼저 지정

2. 0번째 수인 1을 먼저 변수로 지정해놓았으므로, 인덱스 1번 ~ num까지의 범위를 지정하기 위해

   range(1, num + 1)로 지정

3. return_value에 현재 수 + 다음 수를 곱하여 저장하고 return하여 num까지 반복 

 

재귀함수 이용해보기

def multiple(num):
    if num <= 1:
        return num
    return num * multiple(num - 1)

1. num이 1이면 더이상 계산할게 없기 때문에 자기 자신 리턴

2. num이 1이상이면 num을 곱하고 num-1을 multiple에 다시 넣어서 num이 1이되어 리턴될때까지 반복.

multiple(10)

[OUT] : 3628800

 

예제 2]  숫자가 들어있는 리스트가 주어졌을 때, 리스트의 합을 리턴하는 함수 만들기.

참고: 임의 값으로 리스트 만들기 random.sample

(0 ~ 99까지 중에서, 임의로 10개를 만들어서 10개 값을 가지는 리스트 변수 만들기

 

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

random 모듈을 import 하여 임의로 10개 값을 갖는 리스트 만들기

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

 

 

재귀함수 이용해보기

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

len(data) <= 1 이면 리스트의 길이가 1보다 작거나 같으면 하나밖에 없으니까 본인 값 리턴

len(data) > 1 이면 첫번째 리스트값을 더하고 다시 sum_list에 인덱스 1번부터의 리스트를 다시 넣음

계속 반복.

sum_list(data)

[OUT] : 568

예제 3]  회문(palindrome)를 판별할 수 있는 함수를 리스트 슬라이싱을 활용하여

만들기.

 

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

참고 - 리스트 슬라이싱   string = 'Dave'

                                 string[-1] --> e (마지막 문자열)

                                 string[0] --> D (첫번째 문자열)

                                 string[1:-1] --> av (1번인덱스부터 마지막 인덱스 전의 문자열까지)

                                 string[:-1] --> Dav (0번 인덱스부터 마지막 인덱스 전의 문자열까지)

 

def palindrome(string):
    if len(string) <= 1:
        return True
    
    if string[0] == string[-1]:
        return palindrome(string[1:-1])
    else:
        return False

1. 문자열의 길이가 1이하이면 더이상 비교할게 없으니 True로 리턴

2. 첫번째 문자와 마지막 문자가 같을때 다시 palindrome함수로 가서

    다음으로 비교할 1번인덱스부터 마지막 인덱스까지  'string[1 : -1]'로 슬라이싱하여 palindrome에 넣음

    계속 반복 

 

 

프로그래밍 연습 1]  

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

예를 들어 n에 3을 넣으면,3 10 5 16 8 4 2 1 이 됩니다.

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

 

def func(n):
    print (n)
    if n == 1:
        return n #1까지의 계산값을 구하는거니까 1일 때는 1리턴
    
    if n % 2 == 1:
        return (func((3 * n) + 1)) #홀수일때 조건 그대로
    else:
        return (func(int(n / 2))) #짝수일때 조건

1. n이 1일때는 1 리턴

2. n이 홀수일때는 조건대로 3 x n+1을 하고 그 결과값을 다시 func에 넣음

3. n이 짝수일때는 조건대로 n/2를 하고 그 결과값을 다시 func에 넣음

계속 진행하는데 이 과정을 프린트 해야하기 때문에 조건문 제일 위에 print 넣어줌.

func(3)

[OUT] : 3 10 5 16 8 4 2 1

 

 

프로그래밍 연습 2]  

문제: 정수 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

 

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)

 

func(5)

[OUT] : 13

 

 

 

 

 

 

- Fast Campus에서 수강한 내용을 복습하는 게시물입니다.