재귀호출 설명

재귀(Recursion) 알고리즘이란 어떠한 문제를 자기 자신을 호출하여 해결하는 과정을 말합니다.

링크


    예제 1: 코드 실행 추적

    다음은 정보처리산업기사에서 출제된 문제입니다. 다음 코드의 실행 결과는?

    public class RecursiveExample {
        
        public static int recursive(int n) {
            int i;
            if (n < 1)    return 2;
            else {
                i = (2 * recursive(n - 1)) + 1;
                System.out.printf("%d\n", i);
                return i;
            }
        }
        
        public static void main(String[] args) {
            recursive(8);
        }
     
    }
    답:
    
    

    recursive(n-1) 부분이 계속 호출되면서 값을 반환합니다. 최후의 입력값(0)부터 recursive 함수(메소드) 자체에 반환된 값을 대입해 결과를 연쇄적으로 나열하면 됩니다.

    n0인 경우 2를 리턴하고 밑으로는 더 이상 진행되지 않습니다.

    예제 2: 팩토리얼

    package blog.recursive;
    
    public class FactorialExample {
      
      private static int factorial(int n) {
        if(n <= 1) {
          return 1;
        }
        
        return n * factorial(n - 1);
      }
      
      public static void main(String[] args) {
        for(int i = 1; i <= 10; i++) {
          System.out.printf("%d! = %d\n", i, factorial(i));
        }
      }
    
    }
    

     

    예제 3: 배열의 합 계산 (Arrays.copyOfRange 이용)

    package blog.recursive;
    
    import java.util.Arrays;
    
    public class SumOfArray {
      private static int doSum(int[] array) {
        if(array.length <= 1) {
          return array[0]; 
        }
        // Arrays.copyOfRange(array, 시작 인덱스, 끝 인덱스);
        // 시작 인덱스는 포함, 끝 인덱스는 포함하지 않음
        int[] nextTarget = Arrays.copyOfRange(array, 1, array.length);
        return array[0] + doSum(nextTarget) ;
      }
    
      
      public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; 
        System.out.println(doSum(array));
        
        int[] array2 = new int[10];
        for(int i = 0; i < array2.length; i++) {
          int rndNum = (int) (Math.random() * 100 + 1);
          array2[i] = rndNum;
        }
        // for문 없이 배열 출력
        System.out.println(Arrays.toString(array2));
        System.out.println(doSum(array2));
        
      }
    }
    

     

    예제 4: 회문 판별 (스트링 자르기 이용)

    회문(palindrome; 回文: madam이나 nurses run처럼 앞에서부터 읽으나 뒤에서부터 읽으나 동일한 단어나 구)을 판별할 수 있는 프로그램입니다.

    package blog.recursive;
    
    public class Palindrome {
      
      private static boolean checkPalindrome(String word) {
        
        if(word.length() <= 1) {
          return true;
        }
        
        if(word.charAt(0) == word.charAt(word.length() - 1)) {
          // substring(beginIndex, endIndex) -> endIndex는 포함하지 않음
          return checkPalindrome(word.substring(1, word.length() - 1));
        } else {
          return false;
        }
      }
      
      public static void main(String[] args) {
        System.out.println(checkPalindrome("level"));
        System.out.println(checkPalindrome("poop"));
        System.out.println(checkPalindrome("leval"));
      }
    }

     

    예제 5: 패턴으로 결과 찾기

    f(n) = f(n-1) + f(n-2) + f(n-3) 이고, f(1) = 1, f(2) = 2, f(3) = 4 인 것이 알려진 경우 f(n)을 구하는 프로그램 작성

     

    package blog.recursive;
    
    public class Pattern {
      private static int doCalc(int n) {
        switch(n) {
        case 1: 
          return 1;
        case 2:
          return 2;
        case 3:
          return 4;
        default:
          return doCalc(n - 1) + doCalc(n - 2) + doCalc(n - 3);
        }
      }
    
      public static void main(String[] args) {
        for(int i = 1; i <= 10; i++) {
          System.out.printf("f(%d) = %d\n", i, doCalc(i));
        }
      }
    }

    문의 | 코멘트 또는 ayaysir0@naver.com

    donaricano-btn
    카테고리: Java코딩테스트

    1개의 댓글

    트리 순회: 전위, 중위, 후위 (preorder, inorder, postorder) - BGSMM · 2020년 5월 8일 8:19 오후

    […] 재귀함수를 사용하며, 출력 부분의 위치만 바꾸면 전위, 중위, 후위 출력을 결정할 수 있다는 신기한 점(?) 이 있습니다. […]

    댓글 남기기

    이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다