알고리즘 : 재귀 용법(recursive call)

재귀 용법

• 함수 안에서 동일한 함수를 호출하는 형태
• 여러 알고리즘 작성시 사용됨
• 스택의 전형적인 예(함수는 내부적으로 스택처럼 관리됨)

출처 : 위키백과

재귀 용법의 이해

- 팩토리얼을 구하는 알고리즘을 Recursive Call을 활용해서 작성해보자

- 생각해보기
  2! = 1 X 2
  3! = 1 X 2 X 3
  4! = 1 X 2 X 3 X 4
=>규칙 : n! = n X (n-1)!
  1. 함수 만들기
  2. 함수(n)은 n > 1 이면 return n X 함수(n - 1)
  3. 함수(n)은 n = 1이면 return n

=>검증(코드로 구현전에 간단한 경우부터 먼저 검증한다)
  1. 2! 경우
    함수(2)이면, 2 > 1 성립함으로 2 X 함수(1)
    함수(1)은 1 이므로 return 2 X 1 = 2 맞음
 
  2. 3! 경우
    함수(3)이면, 3 > 1 성립합으로 3 X 함수(2)
    함수(2)는 2!, return 2 X 1 = 2
    3 X 함수(2) = 3 X 2 = 3 X 2 X 1 = 6 맞음
 
  3. 4! 경우
    함수(4)이면, 4 > 1 성립합으로 4 X 함수(3)
    함수(3)은 3!, return 3 X 2 X 1 = 6
    4 X 함수(3) = 4 X 6 = 24 맞음

 

예제

def factorial(num):
	if num > 1:
     	return num * factorial(num - 1)
    else:
    	return num

for num in range(10):
	print(factorial(num))
    
"""출력결과
0
1
2
6
24
120
720
5040
40320
362880
"""

 

시간복잡도와 공간복잡도

• factorial(n)은 n - 1번의 factorial()함수를 호출, 곱셈을 함
• 일종의 n - 1번 반복문을 호출한 것과 같음
• factorial()함수를 호출할 때마다, 지역변수 n이 생성됨
• 시간 복잡도/공간 복잡도 O(n - 1)이기 때문에 결과는 둘 다 O(n)

 

#연습문제 재귀함수 활용해서 1부터 n까지 곱이 출력되도록 하라

def mul(n):
	if n <= 1:
    	return n
    return n*mul(n - 1)

mul(10)
#출력결과 3628800