[Algorithm] 재귀함수 (Recursion)

재귀함수 (Recursion)

• 함수 정의에서 자기 자신을 재참조하는 함수이다.
• 큰 덩어리를 작은 덩어리로 나누어 풀 때 사용한다.

 

재귀함수 형태

int Recursion(int n) { 
    1. 기저 사례 (종료조건)
    2. 작업 수행
    3. 재귀 호출
}

int factorial(int n) { 
    if (n === 1) { 
        return 1; 
    } 
    return n * factorial(n-1);
}

 

재귀함수 호출에 따른 스택 변화

• 함수 호출시 새로운 스택프레임이 생성되며 메모리 소모가 발생한다.
• 처음 생성된 스택프레임은 마지막 재귀함수가 종료되기 전까지 유지된다.
• 호출이 많을 경우 스택영역을 벗어나 스택 오버플로우가 발생할 수 있다. (오버플로우가 발생하면 프로그램은 종료된다.)

 

 

재귀함수의 장단점

• 장점
  • 코드가 간결하다.
• 단점
  • 재귀함수 호출이 많을 경우, 큰 메모리 소비와 속도 저하가 발생한다.
  • 똑같은 결과를 반복처리하는 Overlapping Solve Problems이 발생한다.

 

참고

재귀함수의 장점과 단점 그리고 해결책