Recursion 재귀
💫 정의
하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리듬
어떤 문제를 재귀로 푼다는 것은 곧 귀납적인 방식으로 문제를 해결하겠다는 것
귀납적인 방식 -> 일반적인 상식과는 차이가 있다
일반적으로, 순서에 따라 해야할 일이 정해져있는 코드
귀납적으로
제일 앞에 있는 도미노를 쓰러트리면 모든 도미노가 쓰러지겠죠
왜 모든 도미노가 쓰러지는가?
앞에서부터 1번 2번 도미노라고 한다면
- 1번 도미노가 쓰러지면 2번 도미노가 쓰러지고, 2번 도미노가 쓰러지면 3번 도미노가 쓰러지고, … 이런식으로 계속 진행되기 때문에 모든 도미노가 쓰러진다
- 수학적 귀납법
- 1번 도미노가 쓰러진다
- k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다
2번 만을 생각한 후에 바로 모든 도미노가 쓰러진다는 결론에 도달할 수 있어야 한다
즉, 우리가 지금까지 당연하게 생각하던 절차지향적인 사고를 탈피해야 한다
1
2
3
4
5
6
void func1(int n)
{
if (n == 0) return;
cout << n << ' ';
func1(n - 1);
}
절차지향적인 사고로 func1(3) 결과가 왜 3 2 1인지 생각해본다면
이 코드가 동작하는 흐름을 그대로 따라가면 된다
func1(3)이 호출되면 3을 출력하고 func1(2)을 호출
func1(2)이 호출되면 2을 출력하고 func1(1)을 호출
func1(1)이 호출되면 1을 출력하고 func1(0)을 호출
func1(0)이 호출되면 종료
이렇게 과정을 따라가고 나면 func1(3)을 실행했을 때 3 2 1이 출력된다는 것을 알 수 있다
귀납적 사고
func1 함수가 n부터 1까지 차례로 출력하는 함수임을 귀납적인 사고로 이해
- func1(1)이 1을 출력한다. 자명한 사실
- _
- func1(k)가 k k-1 k-2 … 1 을 출력하면, 즉 k부터 1까지 출력하면
- func1(k+1)은 k+1 k k-1 … 1을 출력한다. 즉 k+1부터 1까지 출력한다
이걸 보이는 건 func1(k+1)이 호출될 때 어떤 상황이 생기는가를 보면 되는데
k+1이 출력된 이후 func1(k)가 호출되고 func1(k)는 k부터 1까지 차례로 출력한다 가정을 했으니
func1(k+1)은 k+1부터 1까지 차례대로 출력함을 알 수 있겠죠
이 문장이 참이므로 귀납적으로 func1 함수가 n부터 1까지 차례로 출력하는 함수임을 알 수 있게 돼요
재귀함수의 조건
특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 함 Base Condition/Base Case
모든 입력은 base Condition으로 수렴해야 함
재귀에 대한 정보
- 함수의 인자로 어떤 것을 받고 어디까지 계산한 후 자기 자신에게 넘겨줄지 명확하게 정해야 함
- 모든 재귀 함수는 반복문만으로 동일한 동작을 하는 함수를 만들 수 있음
- 재귀는 반복문으로 구현했을 대에 비해 코드가 간결하지만 메모리/시간에서는 손해를 봄
- 한 함수가 자기 자신을 여러 번 호출하게 되면 비효율적일 수 있음
- 똑같은 연산을, 이미 계산한 값을 여러 번 다시 하게 되는
- 피보나치, n번의 덧셈을 할 것 같지만, 시간복잡도는 O(1.618n), n에 대한 지수함수 꼴
- 다이나믹 프로그래밍을 통해 O(n)에 해결할 수 있다
- 재귀함수가 자기 자신을 부를 때 메모리 영역에서 스택 영역에 계속 누적이 됨
- 문제에서의 메모리 제한이 있는데, 일부 컴파일 환경에서는 스택 영역의 메모리가 별도로 작게 제한되어 있기도 한다
- 재귀로 풀었을 때 메모리 초과가 되면, 어쩔 수 없이 반목문으로 문제를 풀어야 한다
- 참고 : 스택 메모리에는 지역 변수도 들어간다
- 거듭제곱
- 모듈러 연산 ab mod m
- 곱하는 중간중간 계속 m으로 나눠서 나머지만 챙겨가면 된다
231241234 * 12412 * 234의 일의 자리를 구할 때 즉 10으로 나눈 나머지는 일의 자리4 * 2 * 4만 곱해서 구하면 된다는 것을 알고 있다- 모듈러 연산에서는 10이 그냥 m으로 바뀐 것
- ab mod d를 O(b)에 구할 수 있다
- 곱셈
- b가 21억?
- 힌트1 an * an = a2n
- 힌트2 1258 ≡ 4(mod 67) -> 12116 ≡ 16(mod 67)
- 아 귀납법으로 해결할 수 있겠다
- 1번 도미노가 쓰러진다
- k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다
- _
- 1승을 계산할 수 있다
- k승을 계산했으면 2k승과 2k+1승도 O(1)에 계산할 수 있다.
- -> 2k승과 2k+1승 모두 k승을 계산했으면 O(1)에 계산할 수 있다
- 두 문장이 참이기 때문에 a의 임의의 지수승을 귀납적으로 계산할 수 있다
- b가 절반씩 깎이기 때문에 O(log b)
- 하노이 탑 이동 순서
- n-1개의 원판을 기둥1에서 기둥2로 옮긴다
- n번 원판을 기둥 1에서 기둥 3으로 옮긴다
- n-1개의 원판을 기둥 2에서 기둥3으로 옮긴다
- -> 원판이 n-1개일때 옮길 수 있으면 원판이 n개일 때에도 옮길 수 있다
- 원판이 1개일때 원판을 내가 원하는 곳으로 옮길 수 있다
- 원판이 k개일때 옮길 수 있으면 원판이 k+1개일때에도 옮길 수 있다
- 함수의 정의
- base condition
- 재귀식
🫧 _
재귀
반복문과 같은 일을 할 수 있고, 반복문보다 좀 느리고(함수 호출), 더 크지만(호출스택 메모리), 더 명확함
성능을 위해서라면 반복문, 능률을 위해서라면 재귀를
적재적소에 맞게
기본단계 base case : 재귀 함수가 자기 자신을 다시 호출하지 않는 경우
재귀단계 recursive case : 재귀 함수가 자기 자신을 호출
@ 호출 스택
@ 꼬리 재귀 Tail Recursion