728x90
분할 정복 (Divide and Conquer)
분할 정복이란 커다란 문제를 작은 문제들로 쪼개어 작은 문제들을 해결하고, 그에 대한 결과로 커다란 문제를 해결하는 방법입니다.
이는 작은 문제와 큰 문제가 동일한 성격일 때 사용합니다.
(흔히 아는 수학적 귀납법의 반대 순서입니다.)
재귀 함수
재귀함수는 자기 자신을 호출하는 함수입니다.
base case 부분과 재귀 호출 부분으로 구성되어 있으며, 함수가 호출될 때 마다 새로운 스택 프레임이 생성되므로 지역 참조 환경이 달라집니다.
#include <stdio.h>
long factorial(int n) {
if(n == 1) return 1; // base case 부분
return n * factorial(n-1); // 재귀 호출 부분
}
Base Case는 Degenerate Case라고도 부르며, 재귀 호출은 반드시 베이스 케이스에 도달해야 합니다.
그렇지 않으면 스택 오버플로우 오류가 발생합니다.
반복문과의 관계
재귀함수는 반복문으로 표현 가능하며 그 역도 성립합니다.
대부분의 경우 재귀함수를 쓰는 것이 코드가 좀 더 알아보기 쉽고 명확해지나, 재귀함수는 호출될 때마다 새로운 스택프레임을 생성하고 반환시 소멸시키기에 속도, 성능면에서 반복문에 비해 불리합니다.
꼬리 재귀(Tail Recursion, End Recursion)와 머리 재귀(Head Recursion)
머리 재귀
먼저 재귀 호출을 한 이후 되돌아오면서 일(연산을 수행)을 하는 재귀함수입니다.
팩토리얼을 머리 재귀로 구현하면 다음과 같습니다.
#include <stdio.h>
long factorial(int n) {
if(n == 1) return result;
return n * factorial(n-1);
}
꼬리 재귀
먼저 일(연산을 수행)을 한 뒤, 재귀 호출로 들어가는 재귀함수입니다.
팩토리얼을 꼬리 재귀로 구현하면 다음과 같습니다.
#include <stdio.h>
long factorial(int n, int result) {
if(n == 1) return result;
return factorial(n-1, result * n);
}
꼬리 재귀를 하게 되면 머리 재귀에 비해 성능상으로 이점을 가질 수 있는데, 다음 블로그에 자세히 설명이 되어 있습니다.
728x90
'c언어' 카테고리의 다른 글
[C언어] - 문자열 (0) | 2022.04.19 |
---|---|
[C언어] - 배열 (0) | 2022.04.19 |
[C언어] - register, volatile 키워드 (0) | 2022.04.19 |
[C언어] - 스택프레임 (0) | 2022.04.19 |
[C언어] - 지역변수, 전역변수, static 변수 (0) | 2022.04.19 |