[알고리즘] 순환(Recursion)의 개념과 기본 예제 2

인프런 무료 강의 권오흠교수님 '영리한 프로그래밍을 위한 알고리즘 강좌' 보면서 공부한 내용입니다.
부족한 내용이나 잘못된 내용은 댓글남겨주시면 감사하겠습니다!

출처 : https://inf.run/iezc

 

지난 시간에 이어 순환함수를 공부하였다.

2023.06.08 - [알고리즘] - [알고리즘] 순환(Recursion)의 개념과 기본 예제 1

 

오늘은 문자열을 출력하는 함수들을 만들어보았는데, 먼저 문자열의 길이를 계산하는 함수이다.

/*
 * 순환(Recursion)의 개념과 기본 예제 2-01
 * 문자열의 길이 계산 
 * 1) 1+ length("bc") : 1 + 2 = 3 
 * 2) 1+ length("c") : 1 + 1
 * 3) 1+ length("") : 1 + 0
 * -> 3
 */
package edu.recursion;

public class Recursion02_01 {
	public static void main(String[] args) {
		int result = length("abc");
		System.out.println(result);
	}
	
	public static int length(String str){
		if(str.equals(""))
			return 0;
		else
			// str.substring(1) : 문자열에서 앞의 문자를 제거하고 다시 문자열을 만듦
			return 1+length(str.substring(1));
	}
}

str.substring(1) 함수를 이용하여 문자열의 맨 첫글자를 제외하고 다시 문자열을 만든다.

그렇게 위에 주석처럼 반복을 하다보면 문자열의 길이를 구할 수 있는 간단한 함수이다.

 

다음은 문자열을 프린트 해주는 함수인데, 이번에도 substring함수를 이용하였다.

/*
 * 순환(Recursion)의 개념과 기본 예제 2-02
 * 문자열의 프린트
 * -> a
 * 	  b
 * 	  c
 */
package edu.recursion;

public class Recursion02_02 {
	public static void main(String[] args) {
		printChars("abc");
	}
	
	public static void printChars(String str){
		if(str.length() ==0) // 문자열의 길이가 0이라면 출력할 게 없음
			return;
		else{
			// 문자열의 첫 글자 출력 후 나머지 문자열을 담아서 함수 다시 실행 
			System.out.println(str.charAt(0));
			// str.substring(1) : 문자열에서 앞의 문자를 제거하고 다시 문자열을 만듦
			printChars(str.substring(1));
		}
	}
}

 

이번엔 순환함수랑 출력부분을 바꿔서 문자열을 뒤집에서 출력하는 함수이다.

/*
 * 순환(Recursion)의 개념과 기본 예제 2-03
 * 문자열을 뒤집어 프린트
 * -> c
 * 	  b
 * 	  a
 * 
 * 첫 글자를 제외한 문자열을 뒤집어 프린트 한 후 마지막으로 첫 글자를 프린트
 */
package edu.recursion;

public class Recursion02_03 {
	public static void main(String[] args) {
		printCharsReverse("abc");
	}
	
	public static void printCharsReverse(String str){
		if(str.length() ==0) // 문자열의 길이가 0이라면 출력할 게 없음
			return;
		else{
			printCharsReverse(str.substring(1));
			System.out.println(str.charAt(0));
		}
	}
}

 

그리고 다음은 2의 몫과 나머지를 구해서 10진수를 2진수로 변환하는 함수이다. 

/*
 * 순환(Recursion)의 개념과 기본 예제 2-04
 * 2진수로 변환하여 출력
 * -> 1010
 * 
 * 음이 아닌 정수 n을 이진수로 변환하여 인쇄
 * 
 */
package edu.recursion;

public class Recursion02_04 {
	public static void main(String[] args) {
		printInBinary(10);
	}
	
	public static void printInBinary(int n){
		if(n < 2)
			System.out.print(n); // n을 2로 나눈 몫을 먼저 2진수로 변환하여 인쇄한 후
		else{
			printInBinary(n/2);
			
			// 마지막비트는 n을 2로 나눴을 때와 같음, 즉 짝수 : 0, 홀수 : 1
			System.out.print(n%2); // n을 2로 나눈 나머지를 인쇄
		}
	}
}

 

그리고 이전 포스팅했던 순환함수 중 유사한 배열의 합 구하는 함수이다.

/*
 * 순환(Recursion)의 개념과 기본 예제 2-05
 * 배열의 합 구하기
 * -> 15
 * 
 * data[0]에서 data[n-1]까지의 합을 구하여 반환
 * 
 */
package edu.recursion;

public class Recursion02_05 {
	public static void main(String[] args) {
		int[] arr = {1, 2, 3, 4, 5};
		int result = sum(arr.length, arr);
		System.out.println(result);
	}
	
	// n : 배열의 개수, data : 배열
	public static int sum(int n, int[] data){
		if(n <= 0)
			return 0;
		else{
			return sum(n-1, data) + data[n-1];
		}
	}
}

 

그리고 마지막은 스캐너를 이용하여 정수를 읽어 오는 함수인데, 이것은 실제론 잘 사용하지 않는다고 한다.

이렇게도 쓸 수 있다. 알아만 두자!

/*
 * 순환(Recursion)의 개념과 기본 예제 2-06
 * 데이터파일로부터 n개의 정수 읽어오기
 * 잘 사용하지는 않음. 이렇게 할 수도 있다 정도만!
 * 
 * Scanner in이 참조하는 파일로부터 n개의 정수를 입력받아 배열 data의 data[0], ..., data[n-1]에 저장
 * 
 */
package edu.recursion;

import java.util.Scanner;

public class Recursion02_06 {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int size = 3;
		int[] arr = new int[size];
		readFrom(size, arr, in);
	}
	
	// n : 배열의 개수, data : 배열
	public static void readFrom(int n, int[] data, Scanner in){
		if(n == 0)
			return ;
		else{
			readFrom(n-1, data, in);
			data[n-1] = in.nextInt();
		}
	}
}

 

 모든 순환함수는 반복문(iteration)으로 변경 가능
 그 역도 성립. 즉 모든 반복문은 recursion으로 표현 가능
 순환함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현하는 것을 가능하게 함
 하지만 함수 호출에 따른 오버해드가 있음
 (매개변수 전달, 액티베이션 프레임 생성 등)