재귀 호출

반복(Iteration)과 재귀(Recursion)

• 반복과 재귀는 유사한 작업을 수행할 수 있다.
• 반복은 수행하는 작업이 완료될 때까지 계속 반복
  • 루프(for/while, do~while 구조)
    
    
• 재귀는 주어진 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용하는 방법
  • 하나의 큰 문제를 해결할 수 있는(해결하기 쉬운) 더 작은 문제로 쪼개고 결과들을 결합한다.
  • 재귀 함수로 구현

재귀 함수(recursive function)

• 함수 내부에서 직접 혹은 간접적으로 자기 자신을 호출하는 함수
• 완전 탐색을 위한 순열/조합 DFS 등에 사용된다.
• 일반적으로 재귀적 정의를 이용해서 재귀 함수를 구현한다.
• 따라서, 기본 부분(basis part)와 유도 파트(inductive part)로 구성된다.
• 재귀적 프로그램을 작성하는 것은 반복 구조에 비해 간결하고 이해하기 쉽다.
  • 근데 어려운데..??
• 함수 호출은 프로그램 메모리 구조에서 스택을 사용!
• 따라서 재귀 호출은 반복적인 스택의 사용을 의미하며 메모리 및 속도에서 성능저하가 발생한다.

팩토리얼 재귀 함수

• n! 에 대한 재귀함수

int fact(int n){
	if (n<=1)
    	return 1;
    else
    	return n * fact(n-1);
}

함수 호출과 작업 진행

• 함수들은 호출되면서 스택에 함수만을 위한 메모리 공간 확보
• 실행하고 싶은 작업은 재귀 호출 앞이나 뒤에 작성 가능
  • 호출 전에 작성된 내용은 함수가 호출 되면서 순차적으로 실행
  • 호출 뒤에 작성한 내용은 함수가 종료되고 이전 함수로 돌아가는 역순으로 실행
• 재귀함수에서 객체 참조
  • 재귀함수가 호출되면 지역, 매개변수는 매번 새로 생성
  • 반면 객체들은 힙에 생성되며 여러 메서드 영역에서 공유한다

반복 or 재귀?

• 재귀는 문제 해결을 위한 알고리즘 설계가 간단하고 자연스럽다
  • 추상 자료형(List, tree 등)의 알고리즘은 재귀적 구현이 간단하고 자연스러운 경우가 많다.
• 일반적으로, 재귀적 알고리즘은 반복 알고리즘보다 더 많은 메모리와 연산을 필요로 한다.
• 입력 값 n이 커질수록 재귀 알고리즘은 반복에 의해 비효율적일 수 있다.