교재 : Data Structures and Abstraction with Java
챕터 : Chap 7 - Recursion
Recursion
: 문제를 풀기 위해서 문제를 작게 분리했는데, 반복적으로 이뤄지는 작업이라면 Recursion을 이용할 수 있다.
Recursion에서는 base case를 적절히 설정하는 것이 중요하다.
base case를 어떻게 설정하느냐에 따라서 recursion이 몇 번 될지가 달라지기 때문이다.
[7.3]이 [7.5] 보다 효율적이다.
// [7.3]
public static void countDown(int integer) {
System.out.println(integer);
if (intefer > 1)
countDown(interger - 1);
}
// [7.5]
public static void countDown(int integer) {
if (intefer >= 1) {
System.out.println(integer);
countDown(interger - 1);
}
}
Iterative하게 풀 수도 있는데, 굳이 Recursion을 이용해야 하는 이유는 무엇일까?
countDown 과 같은 것은 Iterative 하게 이용할 수 있다.
그러나 HanoiTower를 iterative하게 구현한다면, 너무 복잡해진다.
즉, Recursive하게 표현했을 때 굉장히 쉬워지는 경우가 있기 때문이다.
Recursion은 Stack 과 같은 방식으로 실행된다.
가장 처음에 호출된 함수는 가장 마지막에 끝난다.
FILO(First In Last Out).
결과는 같지만, 반대로 Recursion을 호출하는 경우
[7.16]과 [7.17]은 똑같이 첫번째 element부터 마지막 element까지 출력한다.
// [7.16]
public static void displayArray(int arr[], int first, int last) {
System.out.println(arr[first] + “ “);
if (first < last)
displayArray(arr, first + 1, last);
}
// [7.17]
public static void displayArray(int arr[], int first, int last) {
if (first <= last) {
displayArray(arr, first, last - 1);
System.out.println(arr[last] + “ “);
}
}
Recursion을 통한 Simple Solution : CASE Hanoi Tower
Alogrithm solveTower(numberOfDisks, startPole, tempPole, endPole) {
if (numberOfDisk > 0) {
solveTower(numberOfDisk - 1, startPole, endPole, tempPole);
Move disk from startPole to endPole
solveTower(numberOfDisk - 1, startPole, tempPole, endPole);
}
}
Recursion을 통한 Poor Solution : CASE Fibonacci
Algorithm Fibonacci(n) {
if (n <= 1)
return 1
else
return Fibonacci(n-1) + Fibonacci(n-2)
}Recursion을 이용할 경우, 반복되는 계산이 중복으로 이뤄지기 때문이다.
