[Udemy] JavaScript 알고리즘 & 자료구조 마스터클래스_Section 7

* 수업은 JS 기반이지만 Python으로 구현

Section 7: 재귀

재귀

재귀란 자기자신을 호출하는 절차이다. 

스택 호출하기

stack은 데이터 구조이다. 어떤 함수를 부르게 되면, call stack 제일 위에 놓여진다. 함수의 return을 받거나, 함수가 끝나면 컴파일러가 그 stack의 제일 위에 있는 항목을 제거한다. 재귀함수는 이와 다르게 계속해서 새로운 함수를 호출 스택에 추가한다.

재귀 함수에서 중요한 2가지

• base case: 재귀가 멈추는 시점
• different input: 매번 다른 데이터를 이용해 함수를 호출하는 것이 필요

팩토리얼 함수

# 팩토리얼 함수 for문으로 구현
def factorial(num):
    # 결과값을 1로 초기화
    total = 1
    
    # i는 주어진 숫자 num부터 1보다 하나 클 때까지 1씩 줄어든다
    # total에 i를 곱한값을 total에 다시 배정한다
    for i in range(num, 1, -1):
        total *= i
    # 결과값을 return
    return total

# 팩토리얼 함수 재귀함수로 구현
def factorial(num):

	# base case: 만약 num이 1 이라면 1을 return
    if num == 1:
        return 1
        
    # different input: 값을 하나 줄여서 재귀함수를 불러오는 부분
    return num * factorial(num-1)

재귀의 잠재적 위험

• base case가 없는 경우
• 잘못된 값을 반환하거나, 반환하는 것을 잊는 경우
• stack overflow: 가능한 stack의 수를 넘어가는 경우

Helper 메소드 재귀

재귀적이지 않은 외부 함수가 재귀적인 내부 함수를 호출하는 패턴이다.

# 홀수인 것을 helper 재귀 함수를 이용해 출력하기
def Odd(arr):
	# 결과 도출용 빈 리스트
    result = []

	# helper 함수
    def helper(helperinput):
    	# 만약 입력값의 길이가 0이라면, 함수를 종료
        if len(helperinput) == 0:
            return
        # 만약 입력값 중 첫 번째를 2로 나눈 것이 0이 아니라면
        # 입력값 중 첫 번째 값을 result 리스트 끝에 삽입
        if helperinput[0] % 2 != 0:
            result.append(helperinput[0])
        
        # helper함수를 그 전에 입력했던 것의 1번째부터(0부터 시작이므로 사실상 두 번째값)으로
        # 실행하라
        helper(helperinput[1:])

	# helper함수를 주어진 입력값으로 실행하라
    helper(arr)
	
    # 결과를 return
    return result
    
    
Odd([1, 232, 44, 35])

순수 재귀

배열은 배열을 복사하는 함수 method를 활용하는 경우, 배열을 변경할 필요없이 결과를 축적해서 활용할 수 있다.

문자열은 변경할 수 없으므로, slice나 substring 등을 이용해 사본을 만들어야 한다.

객체의 경우, (파이썬에서는 dictionary와 유사) dictionary.update(dic2)나 *를 이용한 튜플의 패킹, 언패킹 연산을 사용하는 것이 유용하다.

# *를 이용한 연산
dic = {'a': 1, 'b': 2, 'c': 3}
# dic = {'a': 1, 'b': 2, 'c': 3}

n1, *others = dic
# n1 = 'a'
# others = ['b', 'c']

JS 기반 설명이라 비슷한 Python 함수를 따로 찾을 때 참고할 블로그

# 홀수인 것을 순수 재귀 함수를 이용해 출력하기
def Odd(arr):
	# 결과 도출용 빈 리스트
    result = []

    # 만약 입력값의 길이가 0이라면, 함수를 종료
    if len(arr) == 0:
        return result

    # 만약 입력값 중 첫 번째를 2로 나눈 것이 0이 아니라면
    # 입력값 중 첫 번째 값을 result 리스트 끝에 삽입
    if arr[0] % 2 != 0:
        result.append(arr[0])
    
    # 입력했던 것의 1번째부터(0부터 시작이므로 사실상 두 번째값)으로 실행한 Odd함수를
    # 결과로 연장하라.
    result = result + (Odd(arr[1:]))

    # 결과를 return
    return result
    
Odd([1, 232, 44, 35])