[TIL-20260204] 코딩 테스트 - 재귀 함수 (Recursive Function)

🍀 To Do List

✔️ 코딩 테스트 강의 - 재귀 함수

✔️ 사이드 프로젝트 - token 재발급 엔드포인트 추가중

 

병원 다녀오느라 많이 못 했다. 조급해 하지 말고 꾸준히 해보자 !

 

👩🏻‍💻 Today I Learned ...

 

재귀 함수 (Recursive Function)

• 자기 자신을 호출하는 함수
• 종료 조건 필수
  • 종료 조건이 없으면 무한 루프에 빠져 `Stack Overflow`가 발생 할 수 있다.

 

💡 Tip  로직이 반복되는 구조라면 재귀적으로 구현해보자.

 

 

 

팩토리얼 구현

• 팩토리얼은 1부터 어떤 양의 정수 n까지의 정수를 모두 곱한 것을 의미한다.

 

예를들어 `5!` 는  `5! = 5 × 4 × 3 × 2 × 1 = 120`

수식으로 표현하면 `n! = n × (n-1) × (n-2) × ... × 2 × 1` 이다.

 

이를 코드로 표현하면 아래와 같다.

 

Factorial(5) = 5 × Factorial(4)
Factorial(4) = 4 × Factorial(3)
Factorial(3) = 3 × Factorial(2)
Factorial(2) = 2 × Factorial(1)
Factorial(1) = 1  ← 종료 조건

 

def factorial(n):
    if n == 1:  # ⭐️ 종료 조건 
        return 1
    return n * factorial(n-1)  # 재귀 호출

print(factorial(5))  # 120

 

 

 

회문(Palindrome) 판별 구현

• 회문은 똑바로 읽으나 거꾸로 읽으나 똑같은 단어나 문장을 의미한다.

 

 

 

"abcba" 라는 문자열이 회문인지 판단하는 과정은 아래와 같다.

⬇️      ⬇️  첫번째 글자와 맨 뒤에서 첫번째 글자가 같은지 비교
a b c b a

 ⬇️   ⬇️    두번째 글자와 맨 뒤에서 두번째 글자가 같은지 비교
a b c b a

    ⬇️      마지막 남은 한 글자는 비교 대상 X
a b c b a

 

 

재귀적 사고로 표현하자면 아래와 같다.

⬇️      ⬇️  첫번째 글자와 맨마지막 글자가 같은지 비교
a b c b a

b c b      비교한 글자가 같다면 잘라내서, 비교 범위를 줄인다.

⬇️  ⬇️      첫번째 글자와 맨마지막 글자가 같은지 비교
b c b

c          비교한 글자가 같다면 잘라내서, 비교 범위를 줄인다.

⬇️          마지막 남은 한 글자는 비교 대상 X
c

 

 

같은 글자로 판단되면 해당 글자들을 제외하여 비교 범위를 줄이고, 첫번째 글자와 마지막 글자만 비교하면 된다.

이를 코드로 표현하면 아래와 같다.

 

def is_palindrome(string):
    if len(string) <= 1: # ⭐️ 종료 조건
        return True
    if string[0] != string[-1]:
        return False
    return is_palindrome(string[1:-1])

 

 

 

Python 문자열 슬라이싱

• `문자열[시작인덱스:끝인덱스]` 로 표기
• 문자열의 뒤에서부터 자르고 싶은 경우, 음수 인덱싱을 사용한다.

"가나다라마바사"[0:5] # 가나다라마 
                  # 5번째 인덱스 "전"에서 잘라줌.
"가나다라마바사"[0:6] # 가나다라마바
"가나다라마바사"[0:1] # 가
"가나다라마바사"[3:4] # 라
"가나다라마바사"[0:7] # 가나다라마바사


"가나다라마바사"[1:-3] # 나다라
"가나다라마바사"[1:-2] # 나다라마
"가나다라마바사"[1:-1] # 나다라마바