[recursion 예제 2] 문자열, 2진수

순환(재귀함수)를 이용한 예제를 알아보자.

 

 

1.문자열 길이 계산

 

*c++에서 substr함수는

substr(pos, len) 이다.

//pos는 시작할 위치, len는 몇개를 추출할 건지를 뜻한다.

 

#include <iostream>
#include <string>
using namespace std;
//문자열 길이 계산
int length(string str);
int main(void) {
	int result = length("ImET");
	cout << result << endl;
}
int length(string str) {
	if (str == "")
		return 0; //base case
	else
		return 1 + length(str.substr(1));
}

결과: 4

--> 문자열의 길이가 0이 될 때까지, 즉 다 돌때까지

1. 1번째 인덱스부터로 str을 재정의 하면서

(2. 0번째 인덱스의 개수 1을 더한다.)

3. 모든 인덱스의 개수가 더해진다.

모든 문자열 개수가 계산된다.

 

 

 

2.문자열 출력

 

*c++에서 at메소드가 자바의 charAt메소드를 대신한다.

#include <iostream>
#include <string>
using namespace std;
//문자열 프린트
void printChars(string str);
int length(string str);
int main(void) {
	printChars("ImET");
}
void printChars(string str) {
	if (str.length() == 0)
		return; //base case
	else {
		cout << str.at(0);
		printChars(str.substr(1));//recursive case
	}
}

결과: ImET

-> 문자열의 길이가 0이 될 때까지, 즉 다 돌때까지

1. 0번째 인덱스는 출력하고

2. 1번째 인덱스부터로 str을 재정의 함으로써

모든 문자열이 출력된다.

 

 

 

3. 문자열 거꾸로 출력

 

*흥미로운 것은 2번 코드와 한줄만 순서를 바꾸면 3번 코드를 구현할 수 있다는 것이다.

3번 코드의 아이디어

 

#include <iostream>
#include <string>
using namespace std;
//문자열 프린트
void printCharsReverse(string str);
int length(string str);
int main(void) {
	printCharsReverse("ImET");
}
void printCharsReverse(string str) {
	if (str.length() == 0)
		return; //base case
	else {
		printCharsReverse(str.substr(1));//recursive case
		cout << str.at(0);
	}
}

결과: TEmI

-> 문자열의 길이가 0이 될 때까지, 즉 다 돌때까지

1. 1번째 인덱스부터로 str을 재정의 하고

2. 재정의가 모두 완료된 후에

3. 제일 끝까지 인덱스를 간 곳부터 0번째 인덱스 문자 출력한다.

모든 문자열이 거꾸로 출력 완료된다. :-)  

 

 

 

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

 

*음이 아닌 정수 n을 이진수로 변환하여 출력할 때는,

1. n을 2로 나눈 몫을 이진수로 변환하여 출력한 후

2. n을 2로 나눈 나머지를 출력하면 된다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
void printBinary(int n);
int main(void) {
	printBinary(19);
}
void printBinary(int n) {
	if (n < 2)
		printf("%d",n);//base case
	else {
		printBinary(n / 2);
		printf("%d",n % 2);
	}
}

결과: 10011

 

 

 

 

*이 외에도 순환을 이용하여 <데이터파일로부터 n개의 정수 읽어오기>, <배열의 합 구하기> 등을 할 수 있다.

 

 

---

 

순환, 재귀, Recursion VS. 반복 Iteration

 

1. 재귀함수는 반복문으로, 반복문은 재귀함수로 변환이 서로 가능하다.

2. 순환, 재귀함수는 복잡한 알고리즘을 단순하고 알기 쉽게 한다.

BUT, 함수 호출에 따른 오버해드(매개변수 전달, 액티베이션 프레임 설정)등이 있다. 

 

 

 

 

---

c언어랑 c++ 뒤죽박죽 쓰려니까 헷갈려 죽겠다.

왜이렇게 재귀의 중요성을 강조하는지 궁금하다. 다음 강의가 궁금해!