재귀 함수 - 팩토리얼!, 회문 검사

재귀 함수

재귀란?

재귀(Recursion)은 자신을 정의할 때 자기 자신을 재참조하는 방법을 말한다.

더 나아가 재귀함수란

정의 단계에서 자신을 재참조하는 함수를 뜻한다는걸 알 수 있다.

어디에 쓸까?

60초부터 0초까지 -1을 하며 print()를 해야할 때와 같은 상황에서

간결하고 효율성 있는 코드를 작성할 때 사용한다. 

 

아래의 예시 코드를 보자

#def count_down(number):
#  print(number)
#  count_down(number - 1)
#  
#count_down(60)  
# 이대로 실행하면 무한히 -1이 되어 Recursion Error를 내게 되므로 아래처럼 탈출 조건을 만들어야 한다.


def count_down2(number):
  if number < 0:
    return
  
  print(number)
  count_down2(number - 1)
  
count_down2(60)

60초짜리 타이머를 구현한다면 위와 같을 것이다. 

 

 

팩토리얼!

재귀함수와 관련된 대표적인 문제인 팩토리얼!에 대해 알아보자

팩토리얼은 1부터 양의 정수 n까지의 정수를 모두 곱한 것을 의미한다.

ex)
3! -> 3 * 2 * 1     -> 3 * 2! = 6
4! -> 4 * 3 * 2 * 1 -> 4 * 3! = 24

따라서 이렇게 나타낼 수 있다.

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

예제

실제 팩토리얼 함수를 만들어 팩토리얼 n!을 구현해보자

def factorial(n):
  if n == 1:	# 이 부분이 없으면 위에서 다뤘던 것처럼 무한히 돌게 된다.
    return 1
  return n * factorial(n - 1)
  # n이 5일 때, 5 * factorial(4)
  # n이 4일 때, 5 * 4 * factorial(3)
  # n이 3일 때, 5 * 4 * 3 * factorial(2)
  # n이 2일 때, 5 * 4 * 3 * 2 * factorial(1)
  # factorial(1) == 1이므로 결국 5 * 4 * 3 * 2 * 1이 되어 120을 리턴하게 된다. 
print(factorial(5))

이렇게 재귀 함수를 통해 팩토리얼을 구현하면 보기도 쉽고 간단하고 효율적인 것을 알 수 있다. 

 

 

회문 검사

회문이란?

앞에서 읽어도, 뒤에서 읽어도 똑같은 말을 회문이라 한다. ex) 기러기, 토마토, 스위스, 인도인, 별똥별, 우영우

회문 검사 using 반복문

어떤 한 문자열 string이 있을 때 회문인지 아닌지 반복문을 통해 검사해보도록 하자

input = "소주만병만주소"

def is_palindrome(string):
    start = 0
    end = len(string)-1
    while start != end:
        print(start, end)
        if string[start] != string[end]:
            return False
        start += 1
        end -= 1

    return True
    
print(is_palindrome(input))

이런 방법도 있고 문자열의 길이를 구해 range로 for문을 돌리는 방법도 있을 것이다.

 

근데 여기서, 재귀 함수의 목적은 문제의 범위를 점점 좁혀가는 것이라고 했는데 

회문 검사에도 사용할 수 있지 않을까?

대답은 yes이다. 

회문 검사 using 재귀 함수

input = "소주만만병한만주소"

def is_palindrome(string):
    if len(string) <= 1:	# 3) 마지막에 한 글자만 남았을 때 한 글자만 있어도 회문이기에 True를 리턴시킨다.
        return True
    if string[0] != string[-1]:		# 1) 양쪽 끝의 글자를 비교 후
        return False
    return is_palindrome(string[1:-1])	# 2) 같다면 양 끝 글자를 자른걸 다시 함수에 넣어 리턴한다. 

print(is_palindrome(input))

이렇게 재귀 함수를 이용해 회문 검사를 해봤다. 

 

 

정리

이처럼 재귀 함수를 통해 팩토리얼!과 회문 검사를 해봤다. 

재귀 함수의 장점을 정리하자면 다음과 같다. 

• 알고리즘 자체가 재귀적인 표현이 자연스러운 경우에 재귀 함수를 쓰는 것이 큰 도움이 된다. ex) 피보나치 수열
• 변수 사용을 줄여준다. 변수의 수를 줄이는 것과 더불어 변수가 가질 수 있는 값의 종류 또는 범위를 정확히 제한하는 것이기에 
  함수를 단순하게 만들고, 불변적으로 유지될 수 있도록 만든다.

단점도 존재하는데 계속 함수를 실행할 경우 원하는 결과는 얻겠지만
결과적으로 메모리를 크게 차지하며 스택오버플로우를 발생시킬 수도 있다. 

이런 단점을 보완한게 꼬리 재귀 라고 하는데 이 부분에 대해서도 나중에 다시 공부해봐야겠다.

 

 

 

 

 

https://velog.io/@tilsong/%EC%9E%AC%EA%B7%80-%ED%95%A8%EC%88%98%EB%8A%94-%EC%96%B8%EC%A0%9C-%EC%8D%A8%EC%95%BC-%ED%95%A0%EA%B9%8C

재귀 함수는 언제 써야 할까?