자료구조와 알고리즘 파트6. 재귀함수

재귀함수

• 함수 정의 내에 같은 이름의 함수가 올 때 이를 재귀함수라 한다.
• 반드시 탈출조건이 있어야 stack overflow를 방지할 수 있다.
• 문제가 반복취소될 때 재귀함수를 사용한다.

예시

• 보신각 카운트다운
• 60 ~ 0까지 세기

def count_down(number):
	if number < 0:         # 만약 숫자가 0보다 작다면, 빠져나가자!
	return

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


count_down(60)

예시2

• 0~n 까지의 합 구하기

def sum(n):
    if n == 0:
        return 0
    return n + sum(n-1)


print(sum(10))

예시3

• 팩토리얼
• 1~n 까지의 곱 구하기

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


print(factorial(5))

예시4

• 희문 검사 - 반복문
• 앞으로 가도 뒤로 가도 똑같은 문자열
• 중간에 한글자가 남았을때도 앞뒤가 같아서 희문 성립

input = "abccba"


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


print(is_palindrome(input))

• 이것을 재귀함수로 나타내면

input = "tomato"

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(input))