글 읽기 - 재귀함수가 값을 어떻게 리터하는 지에 대해 질문이 있습니다.

karlin 7년 전 0

아래의 코드를 제출했더니 AC가 떴는데요

재귀함수가 어떻게 값을 반환하는 건지 잘 모르겠습니다.

재귀함수 solve에서 3으로 나누거나, 2로 나누거나, 1을 빼 거나 셋 중에 하나를

n이 1일 때까지 반복하다가 n이 1일 때 값을 반환을 해도 반환값을 저장하지 않고

재귀함수 끝에도 다른 return문이 없으니까 컴파일 에러가 떠야하는 게 아닌가요?

(궁금한 게 뭔지는 아는데 말로 풀어쓰려니까 어렵네요ㅠㅠ)

#include <stdio.h>

int ans = 1000001;

int solve(int n, int cnt) {
	if (n == 1) {
		if (cnt < ans) {
			ans = cnt; return cnt;
		}
		else return ans;
	}
	else if (n % 3 == 0) solve(n / 3, cnt + 1);

	//else n % 2 ? solve(n - 1, cnt + 1): solve(n / 2, cnt + 1), solve(n - 1, cnt + 1);
	else if (n % 2 == 0) {
		solve(n / 2, cnt + 1); solve(n - 1, cnt + 1);
	}
	else
		solve(n - 1, cnt + 1);
}

int main() {
	int N;

	scanf("%d", &N);
	printf("%d", solve(N, 0));
	
	return 0;
}

yukariko 7년 전 1

네. 기저 조건외에 return 문이 없으니 사실 제대로 동작하지 않는 코드입니다.

실제로 저런 코드가 원인이 되어 틀리는 경우도 종종 있습니다.

이 코드가 AC를 받은것은 우연이라고 볼 수 있죠..

C/C++의 단점이기도 합니다.

내부적으론 레지스터의 값이 곧 리턴에 사용되기 때문에 정답을 나타내는 값이 리턴에 사용되는 레지스터안에 들어있다면

정답이 뜰 수 있습니다.

karlin 7년 전 0

답변 감사합니다!!

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

문제

문제

출처

ICPC

재귀함수가 값을 어떻게 리터하는 지에 대해 질문이 있습니다.

karlin 7년 전 0

yukariko 7년 전 1

karlin 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말