재귀 호출 (Recursive Call): 메서드가 자신을 호출하는 경우.
직접 재귀 (Direct Recursion): 메서드가 직접적으로 자신을 호출하는 경우. 예를 들어, 팩토리얼 계산 같은 경우.
간접 재귀 (Indirect Recursion): 두 개 이상의 메서드가 서로를 호출하여 원래의 메서드로 돌아가는 경우. 예를 들어, 메서드 A가 메서드 B를 호출하고, B가 다시 A를 호출하는 방식.
모든 recursion은 iteration으로 표현가능하고 모든 iteration도 recursion으로 표현 가능하다.
포트란같은 언어는 recursion이 안되고 lisp같은 언어는 iteration이 없다
recursion이 iteration보다 efficiency가 낮다. 그래도 recursion을 쓰는 이유는 문제를 더 작은 문제로 만들어서 풀어서 심플하게 solution을 만들 수 있기 때문이다.
특히 트리 구조나 그래프 탐색 같은 경우에는 재귀가 코드의 가독성을 높이고, 구현을 더 간단하게 만들어준다. 포인터 변수를 사용하는 경우, 재귀는 각 단계에서 상태를 유지하는 데 유리해지므로 자연스럽게 재귀적 접근이 선호된다.
if (some condition for which answer is known) {
// base case
solution statement
}
else {
// general case
recursive function call
}
base case: 함수가 자기 안에서 자기자신을 호출하는것을 멈추는 조건. 답이 알려져 있고 재귀없이 표현할 수 있는 경우. 재귀 알고리즘은 반드시 하나이상의 base case가 있어야 함. ↔ general case: 문제가 자신의 더 작은 버전의 문제로 표현되는 경우
점점 더 작은 문제로 줄여나가다가 바로 풀 수 있는 상황 = base case가 나올때까지 진행.
int Factorial ( int number )
// Pre: number is assigned and number >= 0.
{
if ( number == 0) // base case
return 1 ;
else // general case
return number * Factorial ( number - 1 ) ;
}
// Recursive definition of power function
int Power ( int x, int n )
// Pre: n >= 0. x, n are not both zero
// Post: Function value = x raised to the power n.
{
if ( n == 0 )
return 1; // base case
else // general case
return ( x * Power ( x , n-1 ) ) ;
}
무한 재귀 (Infinite Recursion): 함수 호출이 끝나지 않고 계속 반복되는 상황을 피해야 해. 프로그램이 멈추지 않게 만든다.
점진적 접근 (Progressive Approach): 각 재귀 호출은 알려진 답을 찾을 수 있는 상황에 점점 가까워져야 함
// base case가 두개인 경우
int Combinations(int n, int k)
{
if(k == 1) // base case 1
return n;
else if (n == k) // base case 2
return 1;
else
return(Combinations(n-1, k) + Combinations(n-1, k-1));
}
BinarySearch는 반복문을 사용하여 작성할 수도 있고, 재귀를 사용하여 작성할 수도 있다.