[Concept] 재귀 용법

재귀 용법

• 함수 안에서 동일한 함수를 호출하는 형태
• 여러 (고급정렬 포함한) 알고리즘 작성시 사용되므로, 익숙해져야 합니다.
• 스택의 구조와 똑같이 동작이 이루어집니다.
• 파이썬에서 재귀 함수는 깊이가(한번에 호출되는...) 1000회 이하가 되어야 합니다.

 

 

1. 함수를 하나 만든다.
2. 함수(n) 은 n > 1 이면 return n X 함수(n - 1)
3. 함수(n) 은 n = 1 이면 return n

 

예시

• 2!

1. 함수(2) 이면, 2>1 이므로, 2 X 함수(1)

2. 함수(1)은 1이므로, return 2 X 1 = 2

 

• 3!

1. 함수(3)이면, 3>1이므로, 3 X 함수(2)

2. 함수(2)이면, 2>1이므로, 3 X 2 X 함수(1)

3. 함수(1)은 1이므로, return 3 X 2 X 1 = 6

 

psudo 코드

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

 

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

 

 

파이썬 코드

# 일반적인 형태1

def factorial(num):
    if num>1:
        return num * factorial(num-1)   # n! = n * (n-1)!
    else:
        return num

 

# 일반적인 형태2

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

 

두 코드의 결과는 모두 다음과 같습니다.

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) 입니다.

 

---

간단한 문제

1. 1부터 num까지의 곱을 구하시오. (재귀함수 이용)

def multiple(num):
    if num<=1:  # 처음부터 1이면
        return num
    return num * multiple(num-1)
    
multiple(5) # 120


# 반복문을 사용하면,
def multiple(num):
    n = 1
    for i in range(1,num+1):
        n = n * i
    print(n)
    
multiple(5)

 

2. 숫자가 들어있는 리스트의 합을 구하시오. (재귀함수 이용)

import random
data = random.sample(range(100),10)
data   # [18, 86, 19, 85, 38, 47, 71, 84, 63, 72]


def sum_list(data):
  if len(data) == 1:
    return data[0]
  else:
    return data[0] + data[1:]  
    
    
# 결과: 583

 

3. 회문((palindrome)은 순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장을 의미)을 판별하라. (재귀함수 이용)

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

 

4.  정수 n을 입력받아, 아래 알고리즘에 의해 1이 되는 과정을 모두 출력하는 함수를 작성하시오.

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

def func(n):
    print(n)
    if n ==1:
        return n
    if n%2==0:
        return func(n//2)
    else:
        return func(3 * n + 1)
        
        
 func(3) 
 
# 결과
3
10
5
16
8
4
2
1