on
1-2. Recursion의 개념과 기본 예제 (2/3) / 순환함수와 반복문...
1-2. Recursion의 개념과 기본 예제 (2/3) / 순환함수와 반복문...
Recursive Thinking
순환적으로 사고하기
절차적 언어
C언어
프로그램이란 어떤 일을 하는 절차를 기술하는 것 이라는 관점이 들어감
객체지향언어
C++
Java
프로그램이란 객체들 간의 상호작용이다 == 객체들 간의 상호작용이 프로그램이다
수학함수 뿐만이 아니라 다른 문제들도 recursion으로 해결할 수 있다
for, while문 반복문 대신 recursion을 사용해서 해결할 수 있다
이번 시간에는 for, while문을 recursion으로 해결해보는 시간!
* recursion에는 BaseCase, Recursive Case 두 조건이 있어야 무한루프에 빠지지 않는다*
Recursion vs Interation
모든 순환함수는 반복문(interation)으로 변경 가능
그 역도 성립함.
즉 모든 반복문은 recursion으로 표현 가능.
순환함수는 복잡한 알고리즘을 단순하고 알기 쉽게 표현 가능
=> 실행 속도는 반복문에 비해 느릴지라도 깔끔한 표현 가능
하지만 recursion은 함수 호출에 대한 오버헤드가 있음 (매개변수 전달, 액티베이션 프레임 생성 등)
=> 반복문에 비해 실행 속도에 관한 손해가 있다는 뜻
모 문자열
(모 문자열의길이-1) + 1 = 모 문자열의 길이
if the string is empty
return 0; (BaseCase)
else
return 1 plus the length of the string that
excludes the first character;
// 원래 문자열에서 첫번째 문자열을 제거한 그 문자열의 길이를 제거한 다음
거기에 1을 더하면 된다 -> 순환적인 문자열 계산 알고리즘
위의 내용을 자바 코드로 표현
public static int length(String str) {
if(str.equals(""))
return 0;
else
return 1 + length(str.substring(1));
}
length라는 함수는 입력으로 String str 문자열을 받아서 그 문자열의 길이를 계산하는 메소드인데
Base케이스는 문자열 길이가 0라면 0을 리턴하고
그렇지 않다면 substring(1)메소드를 통해 첫 문자열만 제거한 뒤 그 문자열 길이를 1과 합치는 것을 0이 되기 전까지 반복한다
** substring(int n)메소드 : 원래 문자열 중 n번 까지의 문자열을 제거하고 나머지 문자열 만드는 메소드
==> substring(1) ==> 원래 문자열에서 첫번째 문자 제거하고 나머지로 문자열 만듦
length("abc");
return 1 + length("ce");
retrun 1 + length("e");
return 1 + length("");
length("") == 0
1 + 0 (return 1 + length("");) == 1
1 + 1 (return 1 + length("e"); == 2
1 + 2 (return 1 + length("ce"); == 3
length("abc"); == 3
두번째 예 ) 문자열의 프린트
public static void printChars(String str) {
if (str.length() == 0)
return;
else {
System.out.print(str.charAt(0));
printChars(str.substring(1));
}
}
입력으로 들어오는 str 문자열을 화면에 출력하는 메소드
BaseCase 문자열이 0면 그냥 return
그렇지 않다면 문자열 첫 글자를 화면에 출력하고
첫 글자를 제외한 문자열을 화면에 출력한다
** str.charAt(0) str문자열의 첫 문자를 리턴해주는 메소드
** str.substring(1) str 문자열에서 첫 문자열 제외하고 리턴
문자열을 뒤집어 프린트
(1) 예를 들어 abcdefg 문자열을 뒤집어 프린트하려면
(2) 먼저 bcd를 뒤집어 프린터한 후 => gfedcb
(3) 마지막으로 첫 글자를 프린트한다 => a
public static void printCharsReverse (String str) {
if (str.length() == 0)
return;
else {
printCharsReverse (str.substring(1));
System.out.print(str.charAt(0));
}
}
BaseCase 문자열 길이가 0 라면 return; 하고 빠져나옴
그게 아니라면
str.substring(1) 문자열을 뒤집어 출력하고
마지막 str.charAt(0)을 출력
2진수로 변환하여 출력
음이 아닌 정수 n을 이진수로 변환하여 인쇄하는 함수
public void printInBinary (int n) {
if (n<2)
System.out.print(n)
else {
printInBinary (n/2);
System.out.print (n%2);
}
}
BaseCase
int n이 2보다 작다면
0, 1 중 하나다
0, 1은 어차피 그 자체로도 2진수이기 때문에 n 그 자체를 출력한다
- n을 2로 나눈 몫을 먼저 2진수로 변환하여 인쇄한 후
printInBinary(n/2);
- n을 2로 나눈 나머지를 인쇄한다
System.out.print(n%2);
n이라는 정수를 2진수로 바꾸게 되면
그중 제일 마지막 비트는 0 혹은 1이다
0 == 짝수
1 == 홀수
n % 2
n을 2로 나누었을 때 나머지가 0이면 짝수, 1이면 홀수다!
즉 마지막의 System.out.print(n%2); 는 2진수의 마지막 비트를 출력하는 것이다!(오오)
그럼 마지막 비트를 제외한 나머지 비트는?
n을 2로 나누었을 때의 몫과 같다
n/2 < n을 2로 나누었을 때의 몫을 리턴 (연산자 /)
printBinary(n/2);
둘을 합치면 2진수가 된다
배열의 합 구하기
public static int sum (int n, int[] data) {
if (n <= 0)
return 0;
else
return sum(n-1, data) + data[n-1];
}
이 예제는 입력으로 하나의 정수 배열(int[] data)이 주어지고
int n은 배열 int[] data에 저장된 데이터의 개수이다
data[0]에서 data[n-1]까지 값이 저장되어 있다고 가정하고
이 함수가 하는 일은 data[0] 에서부터 data[n-1] 까지의 합을 구하여 반환한다
for문 같은 반복문을 사용하지 않고 recursion으로 합을 구해보겠다!
BaseCase는 n이 음수이거나 0이면 0을 반환하는 것
그렇지 않다면
data[0]에서 data[n-2]까지의 합을 계산한 후 : sum(n-1, data)
거기에 마지막 data[n-1]을 더해준다
* sum(n-1, data)
n-1, data를 호출하면
그 전 입력이 data[n-1]이니까
결과적으로 data[n-2]까지의 합을 구해주는 것
보통 recursion 예제로 잘 거론하지 않지만 강사님께서 예를 만들어봄
데이터파일로부터 n개의 정수 읽어오기
Scanner in이 참조하는 파일로 부터
n개의 정수를 입력 받아
data의 data[0] ..... data[n-1]에 저장한다
public void readFrom(int n, int[] data, Scanner in) {
if (n==0)
return;
else {
readFrom(n-1, data, in);
data[n-1] = in.nextInt();
}
}
*Scanner를 데이터파일을 참조한다 == 데이터파일이라고 생각하라
Scanner로부터(데이터파일로부터) n개의 정수를 순서대로 읽어서 배열 데이터int[] data에 저장하는 일을 하는 함수
BaseCase : n이 0이라면 return;으로 빠져나옴
readFrom(n-1, data, in);
먼저 n-1 data를 읽음 ==> data[0] ~ data[n-2]까지 저장
마지막으로 data[n-1] 를 읽어서 배열에 저장
사실 이런 식의 recursion을 쓰는 경우는 없지만 하나의 예로 준비해봄
from http://anityacodiary.tistory.com/132 by ccl(A) rewrite - 2021-09-07 16:27:15