재귀

msung99·2022년 3월 22일

재귀

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

절차지향적 사고

다음 함수에 인풋을 3으로 주면 3 2 1 이 출력되는데, 그 사고 과정을 살펴보자.

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

3 출력 => func1(2) 호출 => 2 출력 => func1(1) 호출 => 출력 => func1(0) 호출

귀납적 사고

위 함수 func1 을 귀납적 사고로 생각해보면, 아래와 같은 귀납적 표현을 증명할 수 있어야한다.

func1(1) 이 1을 출력한다.
func1(k)가 k, k-1, k-2, ... ,1 을 출력하면,
func1(k+1) 은 k+1, k, k-1, ..., 1 을 출력한다.

증명

func1(k+1) 이 호출될 때 어떤 상황이 발생하는가를 생각해보면 된다.
k+1 이 출력된 이후 func1(k) 가 호출되고, func1(k) 는 k 부터 1까지를 차례대로 출력한다고 가정을 했으니,

func1(k+1) 은 k+1 부터 1까지 차례대로 출력함을 알 수가 있다.
이 두 문장이 참이므로, 귀납적으로 func1 함수가 n부터 1까지 차례대로 출력하는 함수임을 알 수 있게된다.

재귀(recursion) 유형에 대한 접근방식

재귀 문제는 귀납적 사고를 통해 반드시 문제를 풀도록 하자.
절차지향적 사고를 가지고 해결하려고 하면, 문제가 복잡할 경우 끝도 없이 구조가 복잡해진다.

재귀 문제는 귀납적 사고로 해결하도록 하자!
마치 도미노 무너뜨리기 처럼,
1) base condition 을 설정하고
2) k번째 항의 결과를 찾아내기 위한 패턴을 찾아내서 점화식을 새운다.
(ex. k번째항의 값 = k-1번째항의 값 x k-2번째항의 값)

실전 문제 해결법
1. base condition 을 설정해야 한다
2. 재귀식을 만들어야 한다. (일정한 패턴을 찾아내 재귀식을 만들것)
3. 함수를 정의해야 한다 (어떠한 기능을 수행하는 함수인지)

재귀 함수의 조건

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

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

예를들어 이 코드를 보면 n = 0 일때 자기 자신을 호출하지 않고 종료가 되므로 이것이 base condition 이다.

우리는 이 함수에 자연수만 넣을테니, 모든 입력은 결국엔 n=0으로 수렴하게 된다.

이 2개의 조건 중 하나라도 어긴다면 재귀 함수는 결과를 내지 못하고 무한히 들어가다가 런타임 에러가 발생하게 될 것이다.

재귀에 대한 정보(팁) 1

함수의 형태를 명확하게 정의해야 함

함수의 인자로 어떤것을 받고 어디까지 계산한 후 자기 자신에게 넘겨줄지 명확하게 정해야 함

모든 재귀 함수는 재귀구조 없이 반복문만으로 동일한 동작을 하는 함수를 만들 수 있다.
재귀는 적재적소에 사용하면 코드가 간결해지지만, 함수 호출이 꽤 비용이 큰 연산이기 때문에 메모리와 시간에서는 손해를 본다.

굳이 재귀를 쓰지 않아도 구현에 큰 어려움이 없으면 재귀 대신 반복문으로 코드를 짜는 것이 좋다.
반대로 재귀 없이 구현하면 코드가 너무 복잡해지는 일부 문제들은 재귀로 구현하는 것이 좋다.

재귀에 대한 정보(팁) 2

한 함수가 자기 자신을 여러 번 호출하게 되면 비효율적일 수 있음
- 중복된 계산을 여러번 반복 : 이미 계산한 것을 또 다시 계산하는 일이 빈번하게 발생해서 시간복잡도가 커짐

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

상식적으로 생각을 해보면피보나치 수열을 구하는 함수는 O(n) 이 걸린다.

그런데 이렇게 피보나치 수열 함수를 재귀로 구현하면 O(1.651^2) 이 걸린다.

예들들어 fibo(5) 값을 구하려는데, (1) fibo(5) = fibo(4) = fibo(3) 이다.

그런데 fibo(4) 의 값을 구하기 위해 fibo(4) = fibo(3) + fibo(2) 로 계산하는데,

식 (1) 에서 이미 fibo(3) 값을 구했음에도 불구하고 또 fibo(3) 을 불필요하게 다시 계산해서 fibo(4) 값을 구해야한다.

재귀에 대한 정보(팁) 3

재귀함수 자신을 계속 호출시 스택 메모리에 누적되므로, 문제에 스택 메모리 제한이 있다면 걸림돌이 될 수있다.

스택 메모리에는 지역 변수도 들어간다.
=> 런타임 에러 발생시 너무 깊은 재귀 호출을 하진 않았는지, 지역 변수로 큰 배열을 생성하지 않았는지등을 봐야한다.

재귀함수가 자기 자신을 부를 때 함수에 대한 정보가 스택 영역에 계속 누적 됨
- 스택 영역 : 메모리 구조에서의 스택 영역
문제를 풀 때 메모리 제한이 있을텐데, 그 제한이 512MB 라고 하면 프로그램이 점유하는 메모리가 최대 512MB 이여야 한다.
그런데 일부 컴파일 환경에서는 스택 영역의 메모리가 별도로 1MB로 제한되어 있기도 하다.
- 예를들어 visual stdio 2017/2019 에서도 별도로 설정을 안하면 1MB이다.
- BOJ 는 메모리 제한이 없지만, SW Expert Academy의 경우 제한이 걸려있다.
- 만약 SW Expert Academy와 같이 스택 메모리가 작게 제한되 곳에서 문제를 푸는 경우 본인의 풀이가 깊게 재귀를 들어가는 풀이라면 어쩔수없이 반복문으로 문제를 풀어야함
스택 메모리에는 지역 변수도 들어감
- BOJ 에 제출하면 "맞았습니다" 가 뜨는 남의코드를 로컬에서 돌렸을 때 계속 런타임 에러가 나는 일을 걲어보는 사람이 자주 있다.
  
  => 가장 의심해 볼만 한것은 재귀가 너무 깊거나,
  지역 변수로 int arr[2000][2000] 과 같이 큰 배열로 잡은 것을 봐야한다.
  - int 가 2000x2000 = 400만개면 벌써 16MB 를 잡아먹기 때문

예시1 - 거듭제곱

a^b mod m

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

int overflow 발생 => 6^100 mod 5 가 정상적인 값은 1인데, 실행 결과는 0이 나옴

=> 해결법 : 곱하는 중간중간 계속 m으로 나눠서 나머지만 챙겨가면 된다.
( + 타입도 int가 아닌 long long 으로 바꿔준다.)

ex) 234236116 x 257421 x 25123 의 일의 자리 ( 즉, 10으로 나눈 결과 ) = 각 수의 일의자리 곱하기 6x1x3 = 8

우리는 각 a x b x c 의 일의 자리, 즉 10으로 나눈 나머지는 숫자 a,b,c의 일의 자리를 구한후 그들을 곱하면 된다는 것을 알고 있기 때문이다.
지금 코드도 10이 m으로 달라졌다는 것 뿐이지, 우리가 상식적으로 알고있는 내용 그대로다.

개선 코드

long long func1(long long a, long long b, long long m){
  long long val = 1;
  while(b--)
    val = val * a % m; // 각 숫자의 나머지만 계속 곱해줌
  return val;
}

m 미만의 수를 2개를 곱하는 상황이 계속 발생하니 m이 2^32 보다 크면
long long의 범위조차 넘어설 수 있다.

=> 이런 경우 _ _128 을 사용하면 된다.
결론적으로 a^b mod m 을 O(b) 에 구할 수 있다.

만일, b의 값이 최대 20억이라서 O(b) 로는 해결할 수 없는 경우는 어떻게 해결하는가?

a를 b번 곱하는 방식은 분명 시간 초과가 발생한다.

msung99

블로그 이전 : https://haon.blog

이전 포스트

DFS (다차원 배열)

다음 포스트

재귀

재귀