재귀 용법(recursive call, 재귀 호출)

1. 재귀 용법 (recursive call, 재귀 호출)

• 함수 안에서 동일한 함수를 호출하는 형태
• 여러 알고리즘 작성시 사용되므로, 익숙해져야 함

2. 예제

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

 

분석

• 간단한 경우부터 생각해보기
  • 2! = 1 X 2
  • 3! = 1 X 2 X 3
  • 4! = 1 X 2 X 3 X 4 = 4 X 3!
• 규칙이 보임: n! = n X (n - 1)!
  1. 함수를 하나 만든다.
  2. 함수(n) 은 n > 1 이면 return n X 함수(n - 1)
  3. 함수(n) 은 n = 1 이면 return n
• 검증 (코드로 검증하지 않고, 직접 간단한 경우부터 대입해서 검증해야 함)
  • 먼저 4! 부터
    • 함수(4) 이면, 4 > 1 이므로 4 X 함수(3)
    • 함수(3) 은 결국 2번에 의해 3 X 2 X 1 = 6
    • 4 X 함수(3) = 4 X 6 = 24 !!

코드

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

for n in range(10):
	print(factorial(n))

>>>
0
1
2
6
24
120
720
5040
40320
362880

시간, 공간 복잡도

• factorial(n) 은 n - 1 번의 factorial() 함수를 호출해서, 곱셈을 함

  • 일종의 n-1번 반복문을 호출한 것과 동일
  • factorial() 함수를 호출할 때마다, 지역변수 n 이 생성됨

• 시간 복잡도/공간 복잡도는 O(n-1) 이므로 결국, 둘 다 O(n)

 

3.재귀 호출 일반적인 형태 

#일반적인 형태 1
def function(입력):
	if 입력 > 입력값: #입력이 일정 값 이상이면
    	return function(입력 -1) #입력 보다 작은 값
    else:
    	return 일정값, 입력값, 또는 특정값 #재귀 호출 종료

#일반적인 형태2
def function(입력):
	if 입력 <= 일정값: #입력이 일정값보다 작으면 
    	return 일정값, 입력값 또는 특정 값 #재귀호출 종료
    function(입력보다 작은 값)
    return 결과값

def factorial(num):
	if num <= 1:
    	return num
    return num * factorial(num - 1)
 

for num in range(10):
	print(factorial(num))
>>>
0
1
2
6
24
120
720
5040
40320
362880

 

함수는 내부적으로 스택처럼 관리

 

4. 알고리즘 

1) 1부터 num 까지 곱이 출력되게 생성

>>>def multiple(num):
	if num <= 1:
    	return num
    return num * multiple(num -1)
    
>>>multiple(20)
2432902008176640000

 

2)  숫자가 들어있는 리스트가 주어졌을 때, 리스트의 합을 리턴하는 함수로 만듬 

##임의 값으로 리스트 생성하는 방법

import random

data = random.sample(range(100), 10)
data

[15, 18, 57, 89, 17, 28, 23, 73, 75, 60]

<알고리즘>

def sum(data):
	if len(data) <= 1:
    	return data[0]
    return data[0] + sum(data[1:])
    
>>>sum(data)
455

 

3)  회문 판별할 수 있는 함수를 재귀함수로 생성

##회문(palindrome)이란? : 순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장 의미 / 리스트를 슬라이싱 활용하여 만듬

def palidrome(string):
	if len(strung) <= 1:
    	return True
    
    if string[0] == string[-1]:
    	return palindrome(string[1:-1])
    else:
    	return False

 

4) 정수 n 이 홀수면 3*n +1 , 짝수이면 n/2 => n이 결국 1이 될 때까지 계속 반복하여 1이 되는 모든 과정 출력

 

ex) 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

def func(n):
	print(n)
    if n == 1:
    	return n
    
    if n % 2 == 1:
    	return (func((3*n) +1))
    else:
    	return (func(inf(n/2)))
        
>>>func(3)
3
10
5
16
8
4
2
1