record logo record

Algorithm

재귀(recursive)

update: 28 June 2020

재귀란?

재귀 함수의 조건

void func1(int n) {
    if(n==0) return; // base condition
    cout << n << ' ';
    func1(n-1);
}

재귀 활용 팁1

재귀 활용 팁2

void fibo(int n) {
    if(n<=1) return 1; // base condition
    return fibo(n-1) + fibo(n-2);
}

위 코드의 시간복잡도는 O(1.618^n)으로 비효율적인 코드이다. 이유는 반복된 계산이 여러번 발생하기 때문이다.

재귀 활용 팁3

재귀 연습문제

연습 문제1 - 거듭제곱(a^b mod m)

연습 문제1-코드확인 
using ll = long long;
ll func1(ll a, ll b, ll m) {
    ll val = 1;
    while(b--) val = val * a % m;
    return val;
}
long long 타입을 하지 않는다면 int overflow가 발생할 수 있다. 따라서, a^b mod m 은 O(b)에 구할 수 있다.

연습 문제2 - BOJ 1629 곱셈

연습 문제2-코드확인 
#include <iostream>
using namespace std;
using ll = long long;

ll pow(ll a, ll b, ll c) {
    if(b==1) return a % c; // base condition
    ll val = pow(a, b/2, c);
    val = val * val % c;
    if(b%2 == 0) return val;
    return val * a % c;
}
int main(void) {
    ll a,b,c;
    cin >> a >> b >> c;
    cout << pow(a,b,c);
    return 0;
}
시간복잡도는 b가 절반씩 깎이기 때문에 O(logb) 이다.

연습 문제3 - BOJ 11729 하노이 탑 이동 순서

연습 문제3-코드확인 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;

queue<pi> q;
int n;

void hanoi(int num, int from, int tmp, int to) {
    if(num == 1) {
        q.push({from, to});
    }
    else {
        hanoi(num-1, from, to, tmp);
        q.push({from, to});
        hanoi(num-1, tmp, from, to);
    }
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n;
    hanoi(n,1,2,3);

    cout << q.size() << "\n";
    while (!q.empty()) {
        cout << q.front().first << " " << q.front().second << "\n";
        q.pop();
    }
    return 0;
}

연습 문제4 - BOJ 1074 Z

연습 문제4-코드확인 
#include <stdio.h>
#include <math.h>
using namespace std;
int N, r, c;
int cnt = 0;

void Z(int x, int y, int len) {
	if(x == r && y == c) {
		printf("%d", cnt);
		return ;	
	} 
	if(r < x + len && r >= x && c < y + len && c >= y) {
		Z(x ,y ,len/2);
		Z(x ,y + len/2 ,len/2);
		Z(x + len/2 ,y ,len/2);
		Z(x + len/2 ,y + len/2 ,len/2);
	} else {
		cnt += len * len;
	}
}
int main(void) {

	scanf("%d %d %d", &N, &r, &c);
	Z(0, 0, pow(2,N));
	return 0;
}

References