[중간정리] 1주차 - 재귀 함수, 피보나치 수열, 퀵 정렬, CPU의 PC/ALU

재귀 함수

재귀 함수의 장단점

장점

• 코드가 직관적이고 간결해 이해하기 쉽다.

단점

• 호출 시 추가적으로 메모리를 사용해 메모리 소비가 많고, 과도한 호출 시 스택 오버플로우가 발생할 수 있다.
• 반복문에 비해 실행 속도가 느리다.

 

피보나치 수열 반환 함수

1항부터 n항까지의 피보나치 수열 반환 함수를 반복문/재귀문으로 각각 만들어보기. n이 0~2에 대한 처리는 두 방식 모두 같았다. 다만 n이 3이상일 때 원래 수열을 가지고 계속 덧붙여가느냐(반복문), 직전 n-1에 대한 피보나치 수열을 새롭게 불러와 덧붙여 반환하느냐(재귀문)의 차이가 있었다.

반복문으로 구현한 피보나치 수열 반환 함수

def pivo(n):
    if n == 0:
        return []
    elif n == 1:
        return [1]
    elif n == 2:
        return [1, 1]
        
    arr = [1, 1]
    for i in range(3, n+1):
        arr.append(arr[-1] + arr[-2])
    return arr

재귀문으로 구현한 피보나치 수열 반환 함수

def pivo(n):
    if n <= 0:
        return []
    elif n == 1:
        return [1]
    elif n == 2:
        return [1, 1]
    
    arr = pivo(n-1)
    arr.append(arr[-1] + arr[-2])
    return arr

 

 

퀵 정렬 수행과정 그려보기

책의 퀵 정렬은 우선 가운데 값을 피벗으로 선택한다. 그 뒤, pl과 pr이 엇갈릴 때까지 각각 피벗보다 큰 수, 작은 수를 가리킨다면 둘을 뒤바꾼다.

 

그러면 pl과 pr이 엇갈린 후, 두 개의 그룹이 생기게 된다. 이때 왼쪽 그룹에서 pr과 left가 같은 요소를 가리킨다면 재귀를 종료하고, 아니라면 그 그룹에 대해 재귀적으로 퀵 정렬을 수행한다.

 

이어서 오른쪽 그룹에서 pl과 right가 같은 요소를 가리킨다면 재귀를 종료하고, 아니라면 그 그룹에 대해 재귀적으로 퀵 정렬을 수행한다.

 

실제 퀵 정렬 예시

[3, 1, 2, 5, 3, 1] 에 대해 퀵 정렬을 수행하는 과정

 

 

CPU에서 PC와 ALU가 수행하는 역할

• PC : 다음에 실행할 명령어가 저장되는 레지스터
• ALU : 산술 및 논리 연산을 처리하는 장치. 레지스터에서 값을 받아 연산을 수행한 뒤, 레지스터에 저장한다.