알고리즘 / 기술면접 스터디 공부 - 알고리즘 이론(재귀용법)

1. 재귀용법이란

: 함수 안에서 동일한 함수를 호출하는 형태

* 여러 알고리즘 작성 시 사용되기 때문에, 익숙해져야 함

 

[예제 - factorial]

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

 

[예제 - 시간복잡도와 공간복잡도]

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

  factorial() 함수를 호출할 때마다, 지역변수 n 이 생성됨

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

 

 

 

2. 재귀 호출의 일반적인 형태

(1) 일반적인 형태 1

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

 

(2) 일반적인 형태 2

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

 

(3) 일반적인 형태 3

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

 

 

3. 재귀호출은 스택의 일반적인 예

 

* 파이썬은 재귀 함수 깊이가 1000회 이하가 되어야 함 !

 

 

4. 재귀 용법을 활용한 프로그래밍 연습

 

(1) 다음 함수를 재귀 함수를 완성해서 1부터 num까지의 곱이 출력되게 만드세요.

def multiple(num):
    return_value = 1
    for index in range(1, num + 1):
        return_value = return_value * index
    return return_value

 

재귀용법의 패턴을 써서 해결한다면,

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

 

 

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

def sum_list(data) :
	if len(data) <= 1:
    	return data[0]
        
    return data[0] + sum_list(data[1:])   // 1부터 마지막꺼까지를 sum_list 함수에 다시 한 번 호출

 

 

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

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

 

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