[TIL-1] 재귀함수

1. Recursive function ❤

영어 뜻에서 유추가 가능하듯 자기 자신을 호출하는 함수를 의미

---

2. 이해를 위한 Example

def count_down(number):
    print(number)          # number를 출력하고
    count_down(number - 1) # count_down 함수를 number - 1 인자를 주고 다시 호출한다!

count_down(60)

• 숫자를 Count 하는 함수를 재귀함수로 구현한 것
• 함수 내의 함수가 호출된 것을 보고 재귀함수로 이루어져 있구나 생각할 수 있음
• 여기서 중요한 점은 재귀 함수가 언제 끝날지를 알려줘야 함
• 끝나는 조건을 주지 않을 경우 RecursionError 가 발생함

def count_down(number):
    **if number < 0:
        return**
    print(number)          # number를 출력하고
    count_down(number - 1) # count_down 함수를 number - 1 인자를 주고 다시 호출한다!

count_down(60)

• 종료조건은 if , return을 통해 단순히 빠져나올 수 있음

코드를 간결하고 명확하게 만들 수 있다는 장점이 있음!!

---

3. 재귀함수를 이용한 대표적인 Example

3.1 Example - Factorial

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))

• 매우 간단하게 Factorial을 구현할 수 있음
• 여기서 중요한 점은 반복되는 것이 무엇인지 수식을 생각할 수 있어야 한다는 점
• 수식을 생각했을 때 코드의 구현까지 이루어 질 수 있음

3.2 Example - 회문 검사

회문은 똑바로 읽으나 거꾸로 읽으나 똑같은 단어나 문장을 의미함
Ex) 토마토, 오디오, 아시아, 일요일, 소주만병만주소 등등

• 먼저 def를 이용해 회문이면 True, 아니면 False를 반환하는 함수를 만들 수 있음

input = "토마토"

def is_palindrome(string):
    n = len(string)
		rule = n//2
    for i in range(rule):
        if input[i]!= input[-1-i]:
            return False
    return True

print(is_palindrome(input))

(result)
True

• 쉽게 구현이 가능하지만 이를 재귀함수로도 구현이 가능함
• 재귀함수의 목적은 문제를 점점 좁혀가는 것
• 즉, 반복되는 구조로 문제가 점점 작아지는 것을 인식할 수 있어야 함

input1 = "tomato"
input2 = '소주반병반주소'

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

    return is_palindrome(string[1:-1])

print(is_palindrome(input1))
print(is_palindrome(input2))

(result)
False
True

• 구조가 축소되는 양상을 보이고, 특정 구조가 반복되는 것 같은 양상을 보이면 재귀함수로 풀어볼 생각을 하면 좋다.
• 반드시 종료조건을 생각해야 함

---

4. 재귀함수 더 알아보자!

• 컴퓨터 내부에서 재귀 함수의 수행은 스택 자료구조를 이용한다.
• 함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다.
• 컴퓨터 구조 측면에서 보자면 연속해서 호출되는 함수는 메인 메모리의 스택 공간에 적재되므로 재귀 함수는 스택 자료구조와 같다는 말이 틀린 말이 아니다.
• 1줄 요약 : 재귀 함수는 내부적으로 스택 자료구조와 동일하다

4.1 재귀함수가 왜 스택 구조 인지 증명을 해봄

input2 = '123454321'  # string

cnt = 0

def is_palindrome(string):
    global cnt
    if len(string) <= 1:
        return True
    if string[0] != string[-1]:
        return False
    print('스택 IN -> string:{} cnt:{}'.format(string, cnt))
    is_palindrome(string[1:-1])
    cnt += 1
    print('스택 OUT -> string:{} cnt:{}'.format(string, cnt))

print(is_palindrome(input2))

(result)
스택 IN -> string:123454321 cnt:0
스택 IN -> string:2345432 cnt:0
스택 IN -> string:34543 cnt:0
스택 IN -> string:454 cnt:0
스택 OUT -> string:454 cnt:1
스택 OUT -> string:34543 cnt:2
스택 OUT -> string:2345432 cnt:3
스택 OUT -> string:123454321 cnt:4

• 먼저 재귀함수를 만나기 전까지(스택 IN) 모두 쌓이는 것을 확인할 수 있었음
• 이후 모든 재귀함수가 쌓이고 나서 선입후출(First IN Last OUT)이 되는 것을 확인할 수 있었음
• 이러한 개념은 자연스럽게 DFS 개념으로 확장되는 것을 확인할 수 있음

Stack 구조 + 재귀함수 ⇒ 두가지 개념을 이해해야 DFS를 이해할 수 있음