재귀함수 - 2

[팩토리얼]

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

5! = 5 * 4 * 3 * 2 * 1

 

Factorial(n) = n * Factorial(n - 1)
Factorial(n - 1) = (n - 1) * Factorial(n - 2)
....
Factorial(1) = 1

 

의 구조임

 

def factorial(n):
    if n <= 1:   # 탈출 방법
        return 1
    return n * factorial(n-1)


print(factorial(5))

# 120

재귀함수는 반복을 빠져나갈 수 있는 방법을 꼭 적어줘야 함!!

 

---

[회문 검사]

다음과 같이 문자열이 입력되었을 때, 회문이라면 True 아니라면 False 를 반환하시오.

 

회문은 똑바로 읽으나 거꾸로 읽으나 똑같은 단어나 문장

ex) 토마토, 오디오, 아시아, 일요일, 소주만병만주소, ...

 

[회문의 조건]

첫 번째 글자 = 맨 뒤에서 첫번째 글자

두 번째 글자 = 맨 뒤에서 두번째 글자

...

마지막 남은 가운데 글자는 뭐가 오든 상관 없음

 

 

 

방법 1) 

문자열을 돌면서

맨 앞의 문자와 맨 뒤의 문자

맨 앞에서 두번째 문자와 맨 뒤에서 두번째 문자

...

를 비교

input = "abcba"


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

# True

 

[내가 만든 코드]

input = "abcba"


def is_palindrome(string):
    for i in range(len(string)):
        if string[i] == string[(len(string) - 1) - i]:
            continue
        else:
            return False

    return True


print(is_palindrome(input))

# True

 

 

방법 2)

맨 앞과 맨 뒤를 비교했다면 비교를 완료한 문자들을 모두 제외하고 나머지 남은 그 중간 값들만 비교

is_palindrome("abcba") -> is_palindrome("bcb") -> is_palindrome("c")

-> is_palindrome(string[1:-1])

string[1(첫번째글자):-1(뒤에서첫번째글자)]

 

[탈출 조건]

문자열의 길이가 1보다 작거나 같을 때(문자열이 한글자일 때: 한글자여도 앞으로 읽거나 뒤로 읽어도 같으니 회문임)

-> 참

맨 첫번째 문자와 맨 뒤의 문자가 다를 때

-> 거짓

input = "abcba"


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


# True

 

[내가 만든 코드]

input = "abcba"


def is_palindrome(string):
    n = len(string)
    if n <= 1:
        return True
    if string[0] == string[-1]:
        string = string[1:-1]
        return is_palindrome(string)
    else:
        return False


print(is_palindrome(input))


# True