[알고리즘] 재귀 알고리즘 기본

재귀란?

- 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우에 재귀라고 한다.

- 재귀를 효과적으로 사용하면 이러한 정의뿐만 아니라 프로그램을 간결하고 효율성 좋게 작성할 수 있다.

 

팩토리얼이란?

- 양의 정수를 순서대로 곱한다는 의미로 순차 곱셈이라고도 한다.

- 10!(10의 팩토리얼)은 10 X 9!로 구할 수 있고, 다시 9!은 9 X 8!로 구할 수 있다.

# 양의 정수 n의 팩토리얼 구하기
def factorial(n: int) -> int:
    # 양의 정수 n의 팩토리얼 값을 재귀적으로 구함
    if n > 0:
        return n * factorial(n-1)
    else:
        return 1

if __name__ == "__main__":
    n = int(input("출력할 팩토리얼 값을 입력하세요.: "))
    print(factorial(n))

실행 결과 출력할 팩토리얼 값을 입력하세요.: 3 3의 팩토리얼은 6입니다.

위 코드에서 factorial( ) 함수는 매개변수 n으로 전달받은 값이 0보다 크면 n * factorial(n - 1)의 값을 반환하고, 0과 같거나 0보다 작으면 1을 반환한다.

 

재귀 호출 과정

- 재귀 호출은 '함수 자신'이 아니라 '자기 자신과 똑같은 함수'를 호출한다고 이해하는 것이 좋음. 왜냐하면 함수 자신을 호출하게 되면 끝없이 자신을 호출하는 행위를 하는 것이 되어버리기 때문.

- 재귀에는 직접 재귀와 간접 재귀가 있는데 직접 재귀는 자신과 똑같은 함수를 호출하는 방식이고, 간접 재귀는 a( )함수가 b( )함수를 호출하고 다시 b( )함수가 a( )함수를 호출하는 방식이다.

- 재귀 과정으로 팩토리얼 값을 구하는 문제는 재귀의 원리를 이해하기 위한 예제일 뿐 현실적으로는 적절하지 않다.(오히려 팩토리얼 함수는 재귀로 정의하지 않는 것이 효율적임)