재귀적 정의 알고리즘

재귀 호출을 디버깅해서 Factorial 알고리즘 분석

재귀 호출 알고리즘을 디버깅 모드로 실행시킨 결과다. 브레이크 포인트를 화면에서와 같이 조건문이 실행되기 전과 후에 잡고 디버깅을 하면 factorial() 함수에 대입되는 값을 하나씩 확인할 수 있다. 입력된 값에 따라 돌려받는 값이 어떻게 변하는지 보면 아래와 같이 수식으로 나타낼 수 있다.

factorial(4)

            -> 4 * factorial(4 - 1)

                    -> 3 * factorial(3 - 1)

                             -> 2 * factorial(2 - 1)

                                      -> 1 (n이 1이므로 종료 조건)

                             -> 2 * 1 (factorial(2 - 1), 즉 factorial(1)의 리턴값 1에 기존의 n = 2일 때의 factorial(2) 함수 블록을 빠져나오기 위해 2를 곱하고 2를 리턴한다.)

                    -> 3 * 2 (factorial(3 - 1), 즉 factorial(2)의 리턴값 2에 기존의 n = 3일 때의 factorial(3) 함수

                            블록을 빠져나오기 위해 3을 곱하고 6을 리턴한다.)

             -> 4 * 6 (factorial(4 - 1), 즉 factorial(3)의 리턴값 6에 기존의 n = 4일 때의 factorial(4) 함수 블록을 빠져나오기 위해 4를 곱하고 최종적으로 factorial(4)의 값인 24를 출력한다.)

                           

팩토리얼은 1부터 n까지 연속한 숫자의 곱이다. 팩토리얼을 재귀 호출로 표현하면 다음과 같다.

    1! = 1
    2! = 2 x 1 = 2 x 1!
    3! = 3 x 2 x 1 = 3 x 2!
    4! = 4 x 3 x 2 x 1 = 4 x 3!
    ...

        n! = n x (n-1)!             <- 팩토리얼을 구하려고 다시 팩토리얼을 구함(재귀적 정의)

이것을 1! = 1 그리고 n! = n x (n-1)!이라는 팩토리얼 성질을 이용해서 팩토리얼을 구하는 프로그램이 위의 소스 코드였다. 이게 이전 세션의 스탠퍼드대학에서 강의한 recusion 강좌에서는 c++로 재귀 호출을 하였다. 그리고 후반부에 Power function이라고 하여 베이스(Base, 밑)에 엑스포넌트(Exponent, 지수)를 제곱 계산하는 소스 코드 재귀 호출 방식으로 코딩하였다. 여기서 강사가 재귀 호출 시에 호출된 스택이, 이를테면 5 ^ 3승을 계산하면 스택 프레임이 3번이 발생하고 리턴 값을 받을 때까지 대기(waiting)한다고 하였다. 따라서 무한 재귀가 이루어지면 시스템이 대기 상태의 데드락(Deadlock)에 빠지므로 이러한 코드를 공격 소스로 사용하여 DoS(Denial of Service) 공격에 응용할 수 있겠다.   

참조

이승찬 저. (2017). 모두의 알고리즘 with 파이썬, 서울:(주)도서출판 길벗.