재귀함수는 자기자신을 호출하는 함수이다.
이때 자기자신을 호출하다가 무한 루프에 빠지는 경우도 있다.
무한 루프에 빠지지 않으려면?
- 적어도 하나의 recursion에 빠지지 않는 경우가 있어야 한다. (base case)
- 그외에는 recursion을 반복한다. (recursion case)
순환함수와 수학적 귀납법
정리: func(int n)은 음이 아닌 정수 n에 대해서 0에서 n까지의 합을 올바로 계산한다.
증명:
1. n=0인 경우: n=0인 경우 0을 반환한다. 올바르다.
2. 임의의 양의 정수 k에 대해서 n<k인 경우 0에서 n까지의 합을 올바르게 계산하여 반환한다고 가정하자.
3. n=k인 경우를 고려해보자. func은 먼저 func(k-1) 호출하는데 2번의 가정에 의해서 0에서 k-1까지의 합이 올바로 계산되어 반환된다. 메서드 func은 그 값에 n을 더해서 반환한다. 따라서 메서드 func은 0에서 k까지의 합을 올바로 계산하여 반환한다.
Recursion vs Iteration
- 모든 순환함수는 반복문으로 변경가능
- 그 역도 성립함, 즉 모든 반복문은 recursion으로 표현 가능함
- 순환함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현하는 것을 가능하게 함
- 하지만 함수 호출에 따른 오버헤드가 있음 (매개변수 전달, 액티베이션 프레임 생성 등)
순환적 알고리즘 설계
암시적 매개변수를 명시적 매개변수로 바꿔라
위 경우 순차탐색을 통해 찾으려는 인자의 인덱스를 반환한다.
n은 명시적으로 인자로 주어지면서 어디까지 탐색해야 하는지 알 수가 있다.
하지만 시작 인덱스 0은 인자로 주어지지 않고 0부터 탐색해야 한다고 유추해야하므로 암시적이다.
위 함수는 0 대신 시작 인덱스 begin과 끝 인덱스 end를 명시적 인자로 전달한다.
정리
재귀함수는 자기 자신을 호출하기 때문에 외부에서 호출되는 상황만을 고려해서 작성하면 안되고(암시적 매개변수가 발생하니까), 일반적인 사용을 고려해서 명시적 매개변수를 줘야한다
출처
모든 자료는 권오흠 교수님의 강좌를 참고하였습니다. 링크
#Coder Became Developer