TIL | 알고리즘 기초 #2
재귀 함수(Recursive Function)
-자기 자신을 호출하는 함수
-basecase와 recursive case 나눠서 생각해줘야함 !
# 예시 1
def countdown(n):
if n > 0:
print(n)
countdown(n - 1) # 여기서 재귀함수 걸리면서 n-1으로 반복하게 된다
4
3
2
1
-basecase와 recursive case 나눠서 생각해줘야함 !
팩토리얼 구하기
<재귀적>
#n = 0 인 경우 n! = 1 base case -> 문제가 충분히 작아서 바로 풀수있는 경우
#n > 0 인 경우 n! =(n - 1)! * n recursive case
def factorial(n):
if n == 0:
return 1
return factorial(n * 1) * n
print(factorial(4))
24
<반복문>
def factorial(n):
result = 1
for i in range(1, n + 1):
result = result * i
return result
재귀함수의 단점
-콜스택이 너무 많이 쌓여서 한계점에 도달하게 되는 Stack Overflow Error 발생할 수 있음(재귀 함수 호출이 너무 많으면)
-파이썬은 애초에 콜스택 1000개까지 허가
Call Stack?
함수가 끝나면 어디로 들어갈지 알아야하니 컴퓨터는 내부적으로 위치를 기억해놓는다 → Call Stack 에 저장 → 함수가 끝나면 다시 원래 위치로 돌아와 기록을 지움
피보나치 수열 재귀적으로 구하기
# n번째 피보나치 수를 리턴
def fib(n):
if n == 1 or n == 2:
return 1
return fib(n - 1) + fib(n - 2)
# 테스트: fib(1)부터 fib(10)까지 출력
for i in range(1, 11):
print(fib(i))
# 시간복잡도 O(2^n)
→ 처음해보는 재귀적 함수라 개념이 잘 안되어있는듯, 구글링 + 힌트봐가면서 단계적으로 생각하는 연습
자연수 1부터 n까지의 합 재귀함수로 구하기
# 1부터 n까지의 합을 리턴
def triangle_number(n):
if n == 1:
return 1
return triangle_number(n-1) + n
# 테스트: triangle_number(1)부터 triangle_number(10)까지 출력
for i in range(1, 11):
print(triangle_number(i))'
# 시간복잡도
# 재귀문을 통해서 **triangle_number** 함수는 총 n번 호출되어, O(n)의 시간이 걸림
→ 한번에 작성!!!!!!!!!
일단 바로 구할 수 있는 basecase에 대하여 생각한 뒤, 그 후 값에 대하여 순차적으로 적어보고 2-3번째 값의 관계를 정의했다 !
팔린드롬(실습)
<처음 답안>
def is_palindrome(word):
length_word = len(word)
for i in range(length_word // 2):
if word[i] == word[-i - 1]:
return True
return False
# 테스트
print(is_palindrome("racecar"))
print(is_palindrome("stars"))
print(is_palindrome("토마토"))
print(is_palindrome("kayak"))
print(is_palindrome("hello"))
True
True # 얘 답안이 틀림
True
True
False
—> 왜 틀렸는지 몰라서 이리저리 해보니 첫번째 글자만 비교중 → return이 for문에도 불구하고 조건 첫글자 확인후 True 리턴시켜버림을 확인 → continue 사용해보자! → 구글링 → 하단 답안으로 수정 성공~~!!!
<수정 후 최종답안>
def is_palindrome(word):
length_word = len(word)
for i in range(length_word // 2):
if word[i] == word[-i - 1]:
continue # 조건을 만족하면 계속해서 조건확인
return False # 조건을 만족하지 않는다면 return False
return True # return으로 끝나지 않은 if 조건을 만족하는 것을 True return
# 테스트
print(is_palindrome("racecar"))
print(is_palindrome("stars"))
print(is_palindrome("토마토"))
print(is_palindrome("kayak"))
print(is_palindrome("hello"))
True
False
True
True
False
Author And Source
이 문제에 관하여(TIL | 알고리즘 기초 #2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sihaha/TIL-알고리즘-기초-2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)