[Inflearn] 영리한 프로그래밍을 위한 알고리즘 - 순환 (Recursion) 의 개념과 기본 예제 2

 

예제1. 문자열의 길이 계산

 

코드

import java.util.Scanner;

public class example {
    public static int length(String str) {
        if(str.equals("")) return 0;
        else return 1 + length(str.substring(1));
    }

    public static void main(String[] args) {
        System.out.println(length("mouse"));
    }
}

팩토리얼, 피보나치 수열, 최대공약수를 순환(재귀함수)으로 푼건 익숙해서 아무 생각 없었는데

문자열의 길이 계산을 순환으로 풀어내다니...! 정말 신세계였다. 사고의 확장!!! 너무 재밌어!!!

코딩할 때 문자열에서 앞에 몇 문자를 날리고 뒤의 문자열만 쓰고 싶을 때 substring(num) 형태를 많이 쓰는 것 같다. 메모메모!

 

 

 

예제 2. 문자열의 프린트

코드

import java.util.Scanner;

public class example {
    public static void printChars(String str) {
        if(str.length()==0) return ; // 또는 str.equals("")
        else {
            System.out.print(str.charAt(0));
            printChars(str.substring(1));
        }

    }

    public static void main(String[] args) {
        printChars("mouse");
    }
}

 

 

 

예제 3. 문자열을 뒤집어 프린트

코드

import java.util.Scanner;

public class example {
    public static void printCharsReverse(String str) {
        if(str.length()==0) return ; // 또는 str.equals("")
        else {
            printCharsReverse(str.substring(1));
            System.out.print(str.charAt(0));
        }

    }

    public static void main(String[] args) {
        printCharsReverse("mouse");
    }
}

문자열을 그냥 프린트 하는 것과, 뒤집어서 프린트 하는 로직을 이해해보자.

 

System.out.print(str.charAt(0));    printChars(str.substring(1));

else문의 코드를 맨 앞 문자를 먼저 출력하고, 재귀함수를 호출하면 정방향으로 문자열이 출력되고

 

printChars(str.substring(1));     System.out.print(str.charAt(0));

재귀함수를 호출 호출 호출하면서, 맨 앞 문자 출력이 스택 밑에 쌓이면서 하나씩 꺼냈을 때는 역방향으로 문자열이 출력된다.

 

 

 

예제 4. 2진수로 변환하여 출력

코드

import java.util.Scanner;

public class example {
    public static void printInBinary(int n) {
        if(n<2) System.out.print(1);
        else {
            printInBinary(n/2);
            System.out.print(n%2);
        }
    }

    public static void main(String[] args) {
        printInBinary(15);
    }
}

 

 

 

예제 5. 배열의 합 구하기

코드

import java.util.Scanner;

public class example {
    public static int sum(int n, int[] arr) {
        if(n<=0) return 0;
        else {
            return sum(n-1, arr) + arr[n-1];
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[5];
        for (int i = 0; i < 5; i++) { // arr = [5, 6, 7, 8, 9]
            arr[i] = i+5;
        }
        System.out.println(sum(5, arr));
    }
}

 

 

 

예제 6. 데이터 파일로부터 n개의 정수 읽어오기

 

 

 

 

Recursion vs Iteration