재귀 용법

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
• 검증 (코드로 검증 X, 직접 간단한 경우부터 대입해서 검증)
  1. 먼저 2! 부터
     • 함수(2) 이면, 2 > 1이므로 2 X 함수(1)
     • 함수(1) 은 1 이므로, return 2 X 1 = 2 맞다
  2. 3!의 경우
     • 함수(3)이면, 3 > 1 이므로 3 X 함수(2)
     • 함수(2)는 결국 1번에 의해 2! 이므로, return 2 X 1 = 2
     • 3 X 함수(2) = 3 X 2 = 3 X 2 X 1 = 6 맞다
  3. 4!의 경우
     • 함수(4)이면, 3 > 1 이므로 4 X 함수(3)
     • 함수(3)는 결국 2번에 의해 3 X 2 X 1 = 6
     • 4 X 함수(3) = 4 X 6 = 24 맞다

 

연습 - 코드 레벨로 적어보기

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

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)

3.재귀 호출의 일반적인 형태 (패턴)

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

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

 

재귀 호출은 스택의 전형적인 예

• 함수는 내부적으로 스택처럼 관리된다.

참고: 파이썬에서 재귀 함수는 깊이가(한번에 호출되는...) 1000회 이하가 되어야 함

 

프로그래밍 연습

 

재귀 함수를 활용해서 1부터 num까지의 곱이 출력되게 만드세요

def multi(value):
    if value <= 1:
        return value
    return value * multi(value-1)
    
multi(5)

출력 : 120

 

숫자가 들어 있는 리스트가 주어졌을 때, 리스트의 합을 리턴하는 함수를 만드세요

def sum(data):
    if len(data) <= 1:
        return data[0]
    return data[0] + sum(data[1:]) #슬라이싱 기능

 

회문을 판별할 수 있는 함수를 리스트 슬라이싱을 활용해서 만드세요

회문(palindrome)은 순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장을 의미함

 

참고 - 리스트 슬라이싱

string = 'Dave' string[-1] --> e string[0] --> D string[1:-1] --> av string[:-1] --> Dav

 

코드

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

 

연습1

• 정수 n에 대해
  
  1. n이 홀수이면 3 X n + 1 을 하고,
     
  2. n이 짝수이면 n 을 2로 나눕니다.
     
  3. 이렇게 계속 진행해서 n 이 결국 1이 될 때까지 2와 3의 과정을 반복합니다.
     
• 정수 n을 입력받아, 위 알고리즘에 의해 1이 되는 과정을 모두 출력하는 함수를 작성하세요.

def one(value):
    print(value)
    if value <= 1:
        return value
    
    if value % 2 == 0:
        return one(int(value/2))
    else :
        return one(3*value + 1)

 

연습2

문제: 정수 4를 1, 2, 3의 조합으로 나타내는 방법은 다음과 같이 총 7가지가 있음 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 입력으로 주어졌을 때, n을 1, 2, 3의 합으로 나타낼 수 있는 방법의 수를 구하시오

1, 2, 3 제외하면 f(n) = f(n-1)+f(n-2)+f(n-3) 이라는 법칙이 발견됨

 

코드

def func(value):
    if value == 1:
        return 1
    elif value == 2:
        return 2
    elif value == 3:
        return 4
    
    return func(value-1) + func(value-2) + func(value-3)

func(6)

출력 : 24