[C언어] - 재귀함수

 

 

분할 정복 (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);
}

 

꼬리 재귀를 하게 되면 머리 재귀에 비해 성능상으로 이점을 가질 수 있는데, 다음 블로그에 자세히 설명이 되어 있습니다.

https://velog.io/@dldhk97/%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98%EC%99%80-%EA%BC%AC%EB%A6%AC-%EC%9E%AC%EA%B7%80

재귀함수와 꼬리 재귀