[Algorithm] 재귀 함수 (python)

재귀 함수

자기 자신을 호출하는 함수!

아래 함수는 60~1을 차례로 출력하는 함수이다.

def count_down(number):
    if number < 0:
        return
    print(number)          # number를 출력하고
    count_down(number - 1) # count_down 함수를 number - 1 인자를 주고 다시 호출한다!

count_down(60)

• if문으로 재귀 함수를 탈출하는 지점을 정해주었다.

※ 재귀 함수는 탈출하는 지점을 정해주어야 한다. 안하면 무한으로 자신을 호출하기 때문에 오류 발생

---

팩토리얼

재귀 함수를 활용해서 팩토리얼을 구현할 수 있다.

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

print(factorial(5))

• n-1로 자기 자신을 계속 호출하고, n이 1이되면 탈출하도록 구현했다.

[출력]
120

---

회문 검사

재귀 함수를 활용해서 회문 검사를 구현할 수 있다.

def is_palindrome(string):
    # 문장의 수가 1이하면 true
    if len(string) <= 1:
        return True
    # 문자열 맨앞/ 맨뒤가 다르면 false
    if string[0] != string[-1]:
        return False

    return is_palindrome(string[1:-1])

print(is_palindrome(input))

• 문자열 슬라이싱을 활용해 문장의 첫 문자와 끝 문자를 제외한 나머지 문장을 추출했다.
• 이를 재귀 함수를 통해 회문 검사를 하도록 했다.
  • 함수를 호출할 때마다, 문장의 맨 앞/맨 끝 문자를 비교해 회문 검사를 하고, 다시 함수를 호출

[출력]
True