[알고리즘] Recursive, 재귀 용법, 재귀 함수 사용

재귀용법

• 함수 안에서 동일한 함수를 사용하는 것
• 여러 알고리즘 작성시 사용되기 때문에 익숙해지는 것이 좋음
• 고급 정렬 알고리즘에서 사용함
• 일정 패턴이 존재함
• 재귀함수의 깊이는 1000으로 제한

---

2개의 재귀 함수 비교

def func_1(num):
    if num <= 1:
        return num
    if num % 10 == 0 :
        return num
    else:
        return func_1(num+1)
        
        
func_1(17)

20

---

def func_2(num):
    num += 1
    if num <= 1:
        return num
    if num % 10 == 0 :
        return num
    else:
        func_2(num+1)
        
        
func_2(17)

None

들어온 값을 1씩 더하고 10의 배수가 된다면 return해주는 함수이다.

 

위와 아래의 차이점은 else: 부분의 return의 유무이다

---

return을 선언하지 않으면 자동으로 func2()가 return이 되는게 아니라  None이 return이 되기 때문에 None 값이 나오는 것이다.

 

팩토리얼 구하기

• 2! = 1 x 2
• 3! = 1 x 2 x 3
• 4! = 1 x 2 x 3 x 4

규칙

• n! = n x (n-1)!
  • n > 1, return n x (n-1)
  • n = 1, return n

---

시간복잡도 공간복잡도

• factorial(n) 은 n-1 번 factorial()을 호출하여 곱셈함
  • n-1번 반복문을 호출하는 것과 같음, 호출시 지역변수 n이 생성된
• 시간/ 공간 복잡도는 O(n-1)로 O(n)임

stack

• 재귀용법은 stack 으로 이뤄져 있음
• 재귀함수가 끝나면 한번에 stack return!
• https://pasongsong.tistory.com/56

#팩토리얼 구현
def factorial(num):
    print('a',num)
    if num > 1:
        a = num * factorial(num-1) 
        print('b',num)
        return a     
    else:
        return num

print(factorial(4))

a 4
a 3
a 2
a 1
b 2
b 3
b 4
24

---

코드

형태

#case 1
def function(input):
    if input > threshold:
        return function(input -1) # 상황에 맞게 변경해주기
    else
        return input # 상황에 맞게 변경해주기
    
#case 2
def function(input):
    if input <= threshold:
        return output 
    function(low_input):
    return output

구현

#팩토리얼 구현
def factorial(num):
    if num > 1:
        return num * factorial(num-1)
    else:
        return num

---

연습

1. 1부터 num까지의 곱이 출력되는 함수 만들기

#반복문
def multiple_1(num):
    return_value = 1
    for i in range(1, num+1):
        return_value *= i
    return return_value
    
#재귀용법
def multiple_2(num):
    if num <= 1:
        return num
    return num * multiple_2(num-1)

---

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

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

# 반복문
def sum_1(num):
    sum = 0
    for i in num:
        sum += i
    return sum

# 재귀용법
def sum_2(num):
    if len(num) <= 1:
        return num[0]
    return num[0] + sum_2(num[1:])

---

3. palindrome을 판단할 수 있는 함수 (palindrome 회문 -> 거꾸로 읽어도 제대로 읽어도 같은 단어, 문장) ex) level

#palindrome
def palindrome(str):
    if len(str) <= 1:
        return True
    elif str[0] != str[-1]:
        return False
    del str[0]
    del str[-1]
    return palindrome(str)
    
    #palindrome _2
def palindrome_2(str):
    if len(str) <= 1:
        return True
    elif str[0] != str[-1]:
        return False
    return palindrome(str[1:-1])

---

4. 정수 n에 대해 n이 1이 될 때까지 홀수이면 3*n+1, n이 홀수이면 n/2 를 진행하는 함수 (과정 출력)

def func(num):
    if num == 1:
        print(num)
        return 'done'
    elif num % 2 == 1:
        print(num)
        func(3*num+1)
    else:
        print(num)
        func(num/2)