글 읽기 - 보통 재귀함수는 몇번까지 돌 수 있는 건가요?

goodinet 7년 전 0

아래는 일반적인 첫항이 1이고 둘째항이 2인, 피보나치 수열을 구하는 dp코드입니다.

물론 변수 3개 정도만 써서 간단하게 원하는 답을 구할 수 있지만

dp와 재귀를 공부하고 있다보니 재귀로 구현을 해 보았는데요.

입력값이 최대 1,000,000인데 배열크기를 입력값보다 크게 잡았음에도 불구하고 Segmentation fault: 11가 떠서 질문입니다.

함수가 350,000번 정도밖에 돌지 않더군요.

재귀함수의 깊이는 최대 350,000번인가요? 문제를 풀 때 저 정도 이상의 깊이를 들어가야하는 문제, 또는 입력 값이면 다른 방법을 찾아야 하는 건가요?

#include <cstdio>
#include <cstring>

using namespace std;

int N,cache[1111111];
int MOD = 15746;

int dp(int s){
  if(s==N-1) return 1;
  if(s==N-2) return 2;
  int& ret = cache[s];
  if(ret != -1) return ret;
  ret = (dp(s+2) + dp(s+1)) % MOD;
  return ret;
}

int main(){
  memset(cache,-1,sizeof(cache));
  scanf("%d",&N);
  printf("%d\n",dp(0));
}

sgchoi5 7년 전 0

"재귀 호출에 따른 스택 크기는 계산이 어려우니 1 만번을 초과하지 않도록 한다"라고 배웠는데요....

goodinet 7년 전 0

감사합니다! 재귀 쓸 때마다 몇번 돌 지 생각해보고 해야하려나요ㅠㅠㅠㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

보통 재귀함수는 몇번까지 돌 수 있는 건가요?

goodinet 7년 전 0

sgchoi5 7년 전 0

goodinet 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말