[자료구조] Recursive Thinking

Recursive Thinking

recursive programming

이번 포스트에선 재귀 프로그래밍을 소개할것 이다.

보다싶이 재귀프로그래밍에는 문제 자체내에서 더 작은 문제 발생을 발견하는 것이 포함된다.

Example1

int 1234 를 1 2 3 4 로 한자리씩 떼어서 세로로 출력하려면 어떻게 해야할까?

재귀프로그래밍을 사용하지 않으면 우선 1000으로 나눠서 몫을 출력 나머지중 100으로 나눠서 몫을 출력, 10으로 나눠서 몫을 출력 그리고 나머지 출력하는 방법이 있다. 하지만 해당 int가 천의 자리숫자임을 미리 알아야 가능한 방법이다.

따라서 재귀프로그래밍을 사용해보자

void write_vertical(unsigned int number) {
    if (number < 10)// Stopping case
        cout << number << endl;
    else
    {
        write_vertical( number / 10 );// Recursive Call
        cout << number % 10 << endl;
    }
}

Example2

위 예제(write_vertical)의 확장판으로 모든 정수(음의 정수 포함)를 세로로 써보자.

void super_write_vertical(int number){
    if(number < 0) // 음수면
    {cout << ‘-’ << endl; // -를 붙이고
     super_write_vertical(abs(number));} // 절대값을 씌운다
     //abs는 절대값
    else if (number < 10) // 여기서부터 아래는 똑같음
       cout << number << endl;
    else
    { super_write_vertical( number / 10 ) ;
       cout <<  number % 10 << endl ;
    }
}

따라서 -36이 number면 ‘-‘, ‘3’, ‘6’이 세로로 출력된다.

함수의 활성화 기록

• 메모리블록에 현재 실행 상태를 저장

• 각 함수 호출에 대해 활성화 기록이 생성되어 시스템 스택에 푸시됨

• 계산이 완료되면 함수가 리턴되어야 하는 위치를 지정하는 “리턴 위치”를 포함

• 또한 함수의 지역변수 및 매개변수 값을 포함

Programming Practice

#include <iostream>  // Provides cin, cout
#include <cstdlib>   // Provides EXIT_SUCCESS
using namespace std;

void write_vertical(unsigned int number);
void super_write_vertical(int number);

int main( )
{
    int i;

    cout << "음수가 아닌 숫자를 타이핑해 주세요: ";
    cin >> i;
    cout << "해당 digits의 숫자는:" << endl;
    write_vertical(i);
    
    cout << "음수를 입력해 주세요: ";
    cin >> i;
    cout << "해당 digits의 숫자는:" << endl;
    super_write_vertical(i);

    cout << "Let's get vertical!" << endl;
    return EXIT_SUCCESS;
}


void write_vertical(unsigned int number)
{
    if (number < 10)
        cout << number << endl; 
    else
    {
        write_vertical(number/10);       
        cout << number % 10 << endl;  
    }
}

void super_write_vertical(int number)
{
    if (number < 0)
    {
        cout << '-' << endl; 
        super_write_vertical(abs(number));}
    else if (number < 10)
        cout << number << endl;      
    else
    {
        super_write_vertical(number/10);   
        cout << number % 10 << endl;      
    }
}

다음은 위 코드의 결과다.