[파이썬 기초] 알고리즘의 개념 / 코딩 연습 - 재귀함수의 개념(카운트다운 함수, 팩토리얼 함수)

# 재귀 함수(recursive function) : 자기 자신을 호출하는 함수(반복문은 없음)

 

예시 1) 정수 4부터 1을 호출하는 countdown 함수

 

def countdown(n) :

   if n > 0:

    print(n)

    countdown(n - 1)

 

countdown(4)

 

1) n = 4 > 0 이므로 4가 출력되고 countdown(3) 함수를 호출

2) n = 3 > 0 이므로 3이 출력되고 countdown(2) 함수를 호출

3) n = 2 > 0 이므로 2가 출력되고 countdown(1) 함수를 호출

4) n = 1 > 0 이므로 1이 출력되고 countdown(0) 함수를 호출

5) n = 0 이므로 아무것도 출력되지 않음(if문의 수행부분으로 들어가지 않고 countdown(0)이 종료됨)

 

countdown(0)이 끝나면 countdown(4)까지 순차적으로 종료됨

 

결과적으로

 

4

3

2

1

 

이 호출됨.

 

궁금증 : 1) if n > 0이 아닌 경우에 대해 별도로 정의(else)하지 않았음에도 함수가 정상적으로 종료되는 이유는..?

           2) 왜 여기는 명령문에 print(countdown(4))를 하지 않고 countdown(4)만 했을까..?
           원함수에 print가 포함되어 있어서?

           3) print(countdown(4))를 하게 되면 4부터 None까지 나오는데 차이는?

 

================================================

 

예시2) 자연수 1부터 자연수 n까지의 곱을 계산하는 팩토리얼(factorial) 함수

 

재귀적으로 문제를 푼다는 것 = 같은 형태의 더 작은 문제(부분 문제)를 풀고 그 답을 이용해서 기존 문제를 푸는 것

5! = 1 x 2 x 3 x 4 x 5 = 120

            4! = 1 x 2 x 3 x 4 = 24

                       3! = 1 x 2 x 3 = 6

                                2! = 1 x 2 = 2

                                      1! = 1  

 

* 팩토리얼에서 시작점이 되는 0의 경우 0! = 1 이므로 이 경우를 별도로 구분해 주어야 함

  n = 0인 경우 : n!  = 1             ----- base case       : 부분 문제가 없는 경우

  n > 0인 경우 : n! = (n-1)! x n    ----- recursive case : 부분 문제가 있는 경우

 

def factorial(n):

    if n == 0:

       return 1

    return factorial(n-1) * n

 

print(factorial(4)) 

1) n = 4 > 0 이므로 factorial(3) * 4를 리턴

2) n = 3 > 0 이므로 factorial(2) * 3을 리턴

3) n = 2 > 0 이므로 factorial(1) * 2를 리턴

4) n = 1 > 0 이므로 factorial(0) * 1을 리턴

5) n = 0 이므로 1를 리턴

 

factorial 0이 리턴되면 factorial 4까지 순차적으로 계산됨

 

결과적으로 24가 호출됨

 

================================================

 

재귀함수와 반복문의 차이는?

재귀함수로 해결할 수 있는 문제는 반복문으로도 해결 가능하고, 그 반대도 가능함.

 

다만 내부적 동작 방식에 따라 더 효율적인 함수가 있음.

재귀적으로 너무 많이 호출하게 되면 호출점을 기록하는 call stack이 너무 많이 쌓이게 되고 에러가 발생할 수 있음(stack overflow error, recursion error)