[C++/코테] 재귀

재귀

하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘

 

재귀함수의 조건

• 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 함. (Base condition/case)
• 모든 입력은 Base condition으로 수렴해야 한다.

재귀에 대한 정보

• 함수의 인자로 어떤 것을 받고 어디까지 계산한 후, 자기 자신에게 넘겨줄지 명확하게 정해야 함
• 모든 재귀 함수는 반복문만으로 동일한 동작을 하는 함수를 만들 수 있다.
• 재귀는 반복문으로 구현했을 때에 비해 코드가 간결하지만, 메모리/시간에서는 손해를 본다. 반복문으로 구현할 수 있으면 그걸 사용하는 게 좋음
• 한 함수가 자기 자신을 여러 번 호출하게 되면 비효율적일 수 있다.

피보나치 수열 예

• 재귀함수가 자기 자신을 부를 때 스택 영역(in 메모리)에 함수에 대한 정보가 계속 누적된다.
  → 아래 코드 실행이 잘 되지 않으면, 스택 메모리 제한을 해제 해야 한다.

#include <bits/stdc++.h>
using namespace std;

void func(int a)
{
    if (a == 0)
        return;
    func(a - 1);
}

int main()
{
    func(100000);
    cout << "done";
}

수학적 귀납법

* 절차 지향적 사고: 1→2 →3 →... →n 이라 n까지 도달하겠구나, 라고 과정을 한 단계씩 사고하는 것

* 귀납적 사고: k →k+1 이 성립할 때, 결국 n에 도달할 것이라고 사고하는 것

절차지향적 사고가 아닌, 귀납적 사고는 단계별로 생각해서 일반항을 유추해 내는 것이 아니라, 특정 규칙(ex. 'i에서 k로 이동한다.')이 반복되면 n항에도 적용이 된다는 귀납적 사고를 적용하는 것. 단계별로 어떤 모양이 될지를 고민하지 말 것. 그냥, 냅다, 적용하기.

연습문제

1. 거듭제곱

$6^100 mood 5$ 를 구하고자 func(6, 100, 5)를 입력

int func(int a, int b, int m){
    int val -= 1;
    while(b--) val *= a;
    return val % m;
}

그러나 위 함수의 결과는 1이 아닌 0이 출력되는데, 그 이유는 int overflow 때문이다. $6^100$은 int의 범위(최대 $2^31 -1$)를 넘어갔다. 👉🏻 해결을 위해서는 곱하는 중간마다 m으로 나눠 나머지를 챙겨가면 된다.

using ll = long long;
ll func1(ll a, ll b, ll m){
    ll val = 1;
    while(b--) val = val * a % m;
    return val;
}

그리고 int형이 아닌 long long 형으로 자료형을 바꿔줄 수 있다.

그런데 m이 $2^32$ 보다 크면 long long을 넘어설 수 있는데, 이럴 때는 Big integer 기능이 있는 Python 혹은 Java를 사용하거나 __int28 과 같은 것을 사용해야 한다. 그러나 코테에서 거의 나오지 않는 경우이다.

 

예제 백준 1629 곱셈

단순히 a를 b번 곱하면 int overflow 발생할 수 있음

2023.11.19 - [Algorithm] - [Python/코테] 백준 1629 곱셈

[Python/코테] 백준 1629 곱셈

2. 하노이 탑

하노이 탑 개념 숙지를 위해 아래 사이트를 통해 게임을 미리 진행해보자.

https://www.mathsisfun.com/games/towerofhanoi.html

 

예제 백준 11729 하노이 탑 이동 순서

2023.11.18 - [Algorithm] - [Python/코테] 백준 11729 하노이 탑 이동 순서

[Python/코테] 백준 11729 하노이 탑 이동 순서

3. Z

예제 백준 1074 Z

2023.11.18 - [Algorithm] - [Python/코테] 백준 1074 Z

[Python/코테] 백준 1074 Z

 

 

---

출처: https://blog.encrypted.gg/943

[실전 알고리즘] 0x0B강 - 재귀