순환(RECURSION)의 개념과 기본 예제2

※ 순환적으로 사고하기(Recursive Thinking)

 - Recursion은 수학함수뿐 아니라 다른 많은 문제들도 해결 가능하다.(반복문)

※ 예제

 - 글자 길이구하기

public class ex {

       

       public static void main(String[] args) {

              

              int iLength = getLength("hello");

              System.out.println(iLength);

       }

       

       public static int getLength(String str){

              

              if(str.equals("")){

                     return 0;

              }else{

                     return 1+getLength(str.substring(1));

              }

       }

}

---

 - 글자 거꾸로 출력하기(CASE1)

public class ex {

       

       public static void main(String[] args) {

              

              printReverse("hello");

       }

       

       public static void printReverse(String str){

              

              if(str.length()==0){

                     return;

              }else{

                     printReverse(str.substring(1));

                     System.out.print(str.charAt(0));

              }

       }

}

- 글자 거꾸로 출력하기(CASE2)

public class ex {

       

       public static void main(String[] args) {

              

              printReverse("hello");

       }

       

       public static void printReverse(String str){

              

              if(str.length()==0){

                     return;

              }else{

                     System.out.print(str.charAt(str.length()-1));

                     printReverse(str.substring(0,str.length()-1));

              }

       }

}

**글자 거꾸로 출력하기에서 위의 예제(CASE1)은 인강답안이고 아래 예제(CASE2)는 내가 풀어본 것이다.

    위에서 보다시피 Recursion call을 하는 위치에 따라 내용이 많이 달라질수 있다... Recursion의 심오함이란.....

---

 - 10진수 2진수로 변환하여 출력하기

public class ex {

       

       public static void main(String[] args) {

              

              printBinaryNum(25);

       }

       

       public static void printBinaryNum(int n){

              

              if(n<2){

                     System.out.print(n);

              }else{

                     printBinaryNum(n/2);

                     System.out.print(n%2);

              }

       }

}

---

※ Recursion vs Iteration

 - 모든 순환함수는 반복문(iteration)으로 변경 가능

 - 그 역도 성립, 즉 모든 반복문은 recursion으로 표현 가능함.

 - 순환함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현이 가능하게 함

 - 하지만 순환함수는 함수 호출에 따른 오버헤드가 잇음

 

 **구글링을 통해 알아본 결과 순환함수보다는 반복문이 성능이 더 좋다고 한다.

     하지만 순환함수를 통해 만든 함수보다 반복문을 이용해 만들때 구현하기 힘든 함수가 있다.

     예를 들어 트리탐색 부분을 만든다고 해보자. 순환함수를 통해 만들면 짧고 간결하게 만들 수 있지만 반복문을 

     통해 만든다면 순환함수와 다르게 복잡하게 만들어야 할것이다.

     비록 반복문이 더 성능적으로는 좋다지만 순환함수로 만들어야 좋을 때가 있으니 필요에 따라 사용하자