C++ 재귀함수 알고리즘(+스택 이용)

 

재귀함수와 스택, 스택 프레임에 대한 개념

 

 

 

자연수 N이 주어지면 아래와 같이 출력

 

입력예제

3

 

출력예제

1 2 3

 

 

만약 코드를 이렇게 작성하면

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

void recur(int x) {
    if (x == 0) return;
    else {
        cout << x << " ";
        recur(x-1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    cin >> n;
    recur(n);

    return 0;
}

 

결과가 3 2 1 로 출력된다.

 

 

그러면 1 2 3 으로 출력되게 하려면 어떻게 해야할까?

 

이렇게 두 코드의 위치를 서로 변경해주면 된다. 

 

어떤 원리로 이렇게 되는 것일까?

그 이유는 재귀는 스택이라는 자료구조를 사용하면서 운영하기 때문이다.

 

재귀함수가 스택을 이용한다는 개념은 아주 중요하니까 꼭 유념해두도록 하자

 

그런데 위 그림은 대략 이런 원리로 돌아간다는 거지 재귀함수 스택 개념을 제대로 설명한 것은 아니다.

어떻게 정확하게 재귀함수가 스택을 이용하는 개념을 확인할 수 있을까?

그걸 위해선 '스택 프레임' 개념을 알아야 한다.

 

 

프로그램이 실행되고 함수들은 호출이 될 때 스택에 본인의 호출정보를 기록한다.

그 호출정보들을 스택 프레임이라고 한다.

 

이것이 스택 프레임에 대한 개념이다.

 

 

 

재귀함수(스택)를 이용한 2진수 출력

 

10진수 N이 입력되면 2진수로 변환하여 출력한다.

단, 재귀함수를 이용해서 출력한다.

 

소스코드 :

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

void recur(int x) {
    if (x == 0) return;
    else {
        recur(x / 2);
        cout << x % 2;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    cin >> n;
    recur(n);

    return 0;
}

 

스택 프레임 개념만 알고 있다면 간단하게 재귀함수를 이용해 원하는 결과를 얻을 수 있다.

 

출처 (학습 자료) :

 

it 취업을 위한 알고리즘 문제풀이

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#curriculum