CHAPTER 01 재귀 호출의 이해

1.1 재귀 접근 방법이란?

재귀함수 : 자기 자신을 호출하는 함수 -> 이 과정이 재귀

일반적으로 재귀에서는 함수에서 전체 작업의 일부분을 수행하고, 나머지 작업은 같은 함수를 재귀적으로 호출하는 방식으로 전체 작업이 수행된다. 종료 조건에 도달할 때까지 재귀 호출이 반복된다.

재귀 함수를 사용할 때 주의할 점

1. 재귀에는 항상 종료 조건이 있어야 한다. (없으면 무한 반복이 발생하므로)
2. 재귀 함수는 전체 작업의 일부만 수행하고 나머지는 재귀 호출에 위임한다.

쉬운 코드와 복잡한 코드 중에 선택해야 한다면, 성능이나 메모리의 이점이 있지 않은 한 쉬운 코드가 좋다.

factorial 함수를 재귀/비재귀 함수로 구현해보기

def recursiveFactorial(n) :
  if n <= 1 :
    return n
  else :
    return recursiveFactorial(n-1) * n

def iterativeFactorial(n) :
  num = 1
  for i in range (2, n+1) :
    num *= i
  return num

함수를 작성할 때의 주의사항

1. 함수는 목적 지향적이어야 한다. 어떤 인수에 대해 함수는 의도한 대로 동작해야 한다.
2. 함수가 수행되는 데 필요한 시간은 짧을 수록 좋다.
3. 함수가 사용하는 메모리의 크기는 작을 수록 좋다.
4. 함수는 이해하기 쉬워야 한다. 주석이 없더라도 이해할 수 있어야 이상적인 코드라 할 수 있다.

선행 재귀와 후행 재귀

일반적으로 재귀 함수는 작업을 수행하는 부분과 자신을 재귀 호출하는 부분으로 구성되어 있다.

• 선행 재귀(head recursion) : 함수가 작업을 수행하기 전에 재귀 호출하는 경우
• 후행 재귀(tail recursion) : 마지막에 재귀 호출하는 경우

후행 재귀는 루프를 사용하는 형태로 바꾸기 쉽다. 그러므로 후행 재귀를 사용하여 코드를 작성한 다음에 루프를 사용할 수 있는지 검토하고 가능하면 바꾸는 것이 좋다.

재귀를 사용한 문제 해결

버블 정렬

버블 정렬에서 n개의 원소를 정렬하는 것과 그 다음 n-1개 원소를 정렬하는 것은 인수만 다를 뿐, 같은 문제다. 그러므로 이 문제를 재귀 함수로 해결하기 위한 정의 과정을 정리하면 아래와 같다.

• 함수가 수행해야 하는 작업 : 1회 탐색을 통해 가장 큰 원소를 제일 뒤로 보낸다.
• 큰 문제를 같은 유형의 작은 문제로 정의하기 : n개 원소의 정렬 = 1회 탐색 + n-1개 원소의 정렬
• 종료 조건 : 탐색 대상의 배열의 크기 <= 1

def bubbleSort(arr, n) :
  if (n <= 1) :
    return ;
  
  for i in range(0,n-1) :
    if arr[i] > arr[i+1] : # swap
      temp = arr[i]
      arr[i] = arr[i+1]
      arr[i+1] = temp
  
  bubbleSort(arr, n-1)

arr = [9, 6, 2, 12, 11, 9, 3, 7]
bubbleSort(arr, 8)
print(arr)

연습. 숫자 n의 구구단을 출력해보자

def printTable(n, i = 9) :
  if (i > 1) :
    printTable(n, i-1)
  return print(f'{n} * {i} = {n * i}')

printTable(5)

# 5 * 1 = 5
# 5 * 2 = 10
# 5 * 3 = 15
# 5 * 4 = 20
# 5 * 5 = 25
# 5 * 6 = 30
# 5 * 7 = 35
# 5 * 8 = 40
# 5 * 9 = 45

1.2 재귀 호출과 마무리

프로세스 주소 공간

프로세스 주소 공간 (process address space) : 프로세스가 차지한 메모리의 영역으로 운영체제가 할당한다.

메모리 배치를 알자.

프로그램 실행의 수명주기와 프로그램이 메모리에 어떻게 로드되는지를 명확히 이해하면 여러 문제를 푸는 데 도움이 된다.

static int x = strlen('hello');

위 코드는 컴파일할 때 에러가 발생한다. 왜? 정적 변수는 로드타임에 초기화되는데 함수는 로드타임에 호출할 수 없기 때문이다. 따라서 아래와 같이 코드를 수정해야 한다.

static int x;
x = strlen('hello');

로드타임 변수는 함수의 반환값이나 지역 변수로 초기화할 수 없다.