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

반복문을 이용해서 해결하는 문제를 Recursion으로 해결하는 예제들

 

github.com/VontineDev/OnlineLearning_Algorithm/tree/main/S02_Recursion

VontineDev/OnlineLearning_Algorithm

05. 문자열의 길이 계산

#include <iostream>

using namespace std;

static int length(string str)
{
    if(str=="")
    {
        return 0;
    }
    else
    {
        return 1 + length(str.substr(1));
    }        
}

int main()
{
    string str = "abc";

    cout << length(str) << endl;
  
}

 

06. 문자열을 프린트

#include <iostream>

using namespace std;

static void printChars(string str)
{
    if(str.length()==0)
    {
        return;        
    }
    else
    {
        cout << str.front();
        printChars(str.substr(1));
    }    
}

int main()
{
    string str = "abc";  

    cout << "Printing..." << endl;
    printChars(str);
}

07. 문자열을 뒤집어서 프린트

#include <iostream>

using namespace std;

static void printCharsReverse(string str)
{
    if(str.length()==0)
    {
        return;        
    }
    else
    {        
        printCharsReverse(str.substr(1));
        cout << str.front();
    }    
}

int main()
{
    string str = "abc";  

    cout << "Printing..." << endl;
    printCharsReverse(str);
}

08. 정수를 이진수로 출력

#include <iostream>

using namespace std;

static void printInBinary(int n)
{
    if(n<2)
    {
        cout << n ;      
    }
    else
    {        
       printInBinary(n/2);
       cout<< (n%2);
    }    
}

int main()
{
    int n = 3;  

    cout << "Printing "<< n << " in Binary..." << endl;
    printInBinary(n);
}

09. 배열의 합 구하기

#include <iostream>

using namespace std;
// data[0]에서 data[n-1]까지의 합을 구하여 반환한다
static int sum(int n, int data[])
{
    if(n<=0)
    {
       return 0;  
    }
    else
    {        
      return sum(n-1, data) + data[n-1];
    }    
}

int main()
{
   int n[] = {3,4,5};  

    for(int i =0; i<sizeof(n)/4; i++)
    {
        cout << n[i];
        if(i<(sizeof(n)/4)-1)
        {
            cout << ", ";
        }
        else
        {
            cout << endl;
        }        
    }
    //cout << "size of array is..." << sizeof(n)/4;
    cout << "Sum of array is..." << endl;
    cout << sum(sizeof(n)/4,n) << endl;
}

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

 

스캐너는 예제에 없어서 직접 만들어봄,

데이터의 순서가 거꾸로 담기는건 readFrom함수에서

 

data[n - 1] = in.nextInt();
readFrom(n - 1, data, in);  

   

순서를 뒤바꿨기 때문이다.

 

그러나 반대로 하면 스캐너에 저장된 값 중 맨 첫번째 것만 저장된다. 

 

스캐너의 함수를 고쳐야 하는데 어떻게 할지 고민하는중...

#include <iostream>
#include <vector>
using namespace std;
// Scanner in이 참조하는 파일로부터  n개의 정수를 입력받아 
// 배열 data의 data[0] ~ data[n-1] 에 저장한다.
class Scanner
{
public:
    Scanner(int n)
    {
        pos = 0;
        for (int i = 1; i <= n; i++)
        {
            myVector.push_back(i);
        }
    }

    vector<int> myVector;
    int pos;

    int nextInt()
    {
        int result;
        if (pos < myVector.size())
        {
            result = myVector.at(pos);
            pos++;
            return result;
        }
        else
        {
            cout << "End of data..." << endl;
            cout << "Relocation postion to first" << endl;
        }
    }
};

static void readFrom(int n, int data[], Scanner in)
{
    if (n == 0)
    {
        return;
    }
    else
    {
        data[n - 1] = in.nextInt();
        readFrom(n - 1, data, in);        
    }
}

int main()
{
    Scanner in(5);
    cout << "value saved in Scanner" << endl;
    for (auto it = in.myVector.begin(); it != in.myVector.end(); ++it)
    {
        cout << *it << ",";
    }
   
    cout << endl << endl;
    int data[5];
    readFrom(5, data, in);
    
    cout << "value saved in data" << endl;
    for(int i =0; i<sizeof(data)/4; i++)
    {
        cout <<data[i];
        if(i<(sizeof(data)/4)-1)
        {
            cout << ", ";
        }
        else
        {
            cout << endl;
        }        
    }
}