TIL-047 | Recursion

🌈 Recursion (재귀)

📝 Recursion 이란?

• 자기 자신을 호출하는 함수를 Recursion, 재귀 함수라고 한다.
• 재귀를 사용함에 있어서 주의할 점은 종료 지점을 정의해줘야 한다는점이다. 종료 지점을 정의해주지 않는다면 재귀는 무한 반복된다.
• 파이썬에서는 재귀의 깊이를 1000 이하로 제한하고 있기 때문에 종료 조건이 없으면 RecursionError가 발생한다.

👉 아래의 코드는 n!(factorial) 을 구하는 재귀 함수의 예시이다.

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

📝 Recursion(재귀)은 언제 사용해야 할까?

1. 주어진 문제를 비슷한 구조의 더 작은 단위로 쪼갤 수 있는 경우
   👉 이는 재귀적인 사고를 의미하며, 주어진 문제를 쪼개어 가장 쉬운 문제부터 해결하는 것이 재귀적인 사고의 기초이다.
   👉 Input, Output 값을 정의하고 문제를 단순하게 정의할 수 있어야 한다.
2. 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우

📝 Recursion vs Iteration

👉 모든 재귀 함수는 반복문으로 변환할 수 있다. 하지만 재귀를 적용한 코드가 가독성 측면에서 좀 더 편리하다.

• Recursion과 Iteration 모두 n에 비례하는 복잡도를 가짐 → O(n)
• 반복적인 메소드 호출을 위한 메모리는 한번만 필요하기 때문에 성능면에서 Iteration이 유리하다.
• 코드를 이해하는 가독성 측면과 유지하는 것이 더 중요시 된다면 Recursion이 추천되어 진다. 그러나 자기자신을 호출할 때에 메모리와 CPU 사용 시간이 더 소요 된다.

📝 Recursion & Stack

• Stack(스택)은 데이터를 임시 저장할 때 사용하는 자료구조로, 데이터에 제한적으로 접근할 수 있는 구조이다. 한쪽 끝에서만 자료를 넣거나 뺄 수 있다.
• 스택의 데이터 입력 출력 순서는 LIFO(Last In First Out) 혹은 FILO(First In Last Out)방식이다.
• 재귀함수는 스택의 전형적인 예시이다. 함수를 한 번 돌때마다 그 값이 스택의 형태로 하나씩 쌓이고 출력되면서 결과 값이 반환된다.

📝 Practice

1. Fibonacci(피보나치) 수열

#Recursion
def fibonacci(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else: 
        return fibonacci(n-1)+fibonacci(n-2)
        
print(fibonacci(1)) # 1
print(fibonacci(2)) # 1
print(fibonacci(3)) # 2
print(fibonacci(4)) # 3
print(fibonacci(5)) # 5

• 피보나치 수열에서 n번째 수 를 반환하는 코드 이다.

#Iteration
def fibonacci2(n):
    if n < 2:
        return n
    x, y = 0, 1
    for i in range(n): 
        x, y = y, x+y 
    return x

• 재귀함수가 아닌 반복문을 사용하여 피보나치 수열을 풀이한 코드이다.

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

def totalSum_list(num_list):
    if len(num_list) <= 1:
        return num_list[0]
    return num_list[0] + totalSum_list(num_list[1:])

• 리스트(num_list)의 길이가 1 이하라면 리스트의 요소가 곧 총 합이므로 첫번째 요소를 리턴한다.
• 리스트(num_list)의 길이가 2 이상이라면 리스트의 첫번째 요소를 더하고 totalSum_list에 인덱스 1번 부터 다시 넣어 계속 반복한다.

3. 회문(palindrome)를 판별할 수 있는 함수 만들기

• 회문(palindrome)은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열(sequence of characters) 등을 의미한다. (ex. 12021, rotator)

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

• 문자열의 길이가 1 이하이면 무조건 True를 리턴한다.
• 문자열의 첫 글자와 마지막 글자를 비교하여 동일하면, 문자열의 두번째 글자부터 끝에서 2번째 글자까지 슬라이싱하여 palindrome 함수에 대입한다.
• 이를 반복하여 string이 회문 인지 판별한다.