Python 재귀함수 알고리즘 Factorial, 회문 검사

Factorial

# Factorial(N) = N*Factorial(N-1)
# ...
# Factorial(1) = 1

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


print(factorial(5))

factorial 예시.

 

함수에 5를 넣었을때

5x4x3x2x1 이렇게 작동되어 결과값 120이 나온다.

 

여기서 주의할 점은 탈출 조건을 만들어야 한다.

 

이 경우는 if를 활용하여 n이 1과 같아질 때 1을 돌려주어 함수가 끝난다.

만약 그렇지 않을 경우엔 계속해서 n * factorial(n-1)이 작동되어 곱셈을 더해간다.

---

회문 검사

input = "소주만병만주소"


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

print(is_palindrome(input))

# 재귀 함수의 목적은 문제를 점점 좁혀가는 것

회문이란 거꾸로해도 똑같은 글자다.

 

for문을 돌려서 하나하나 확인해가며 풀 수도 있겠지만, 재귀함수가 더 효율적이다.

 

함수가 발생되었을 때,

 

string의 0번째 인덱스과 string의 -1의 인덱스가 다를 경우는 바로 False를 반환해주면 된다.

 

여기서 -1 인덱스는 배열의 제일 끝부분을 이야기 한다. 스트링은 이렇게 [0], [1]로 각 글자를 따올 수 있다.

 

if

입력받은 글자의 범위가 1보다 같거나 작을 때

True를 반환해 준다.

 

바깥 마지막 return은 재귀함수로 다시 한 번 이 글자의 첫번쨰와 끝번 째를 돌려준다.

 

처음에 '소주만병만주소' 를 넣어 소와 소가 같다면 마지막 return문이 반환되어,

 

주와 주를 비교하게될거고, 그렇게 만과 만을 비교하게 될 것이다.

 

if문에서는 그렇게 반복되어 마지막 글자 1개만 남았을 경우는 True를 반환해주는 것이다.

(참고로 글자 1개짜리도 회문이라고 본다)

 

---

회문검사 For문 예시

input = "tomato"


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

    return True


print(is_palindrome(input))

# 재귀 함수의 목적은 문제를 점점 좁혀가는 것

똑같이 글자의 범위를 정하고,

 

글자의 범위만큼 i값을 돌려

 

만약 글자의 i값과 마지막 값이 일치하지 않다면 바로 False를 반환하고,

 

그렇지 않다면

 

0번째와 n - 0 번째 를 비교 -> 맞다면 다시 반복

1번와 n -1 번째를 비교 -> 맞다면 다시 반복

....

이렇게 되어 for문이 전부 돌아가게 될 경우, True값을 반환해주는 것이다.