재귀 함수(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