재귀함수 내 i++와 i+1의 차이점을 알고 싶습니다.

mute_x.s의 이미지

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable : 4996)
 
//2748
 
int n, m, num[21] = { 0, }, count = 0;
 
void func(int i, int sum) {
	if (i < n) {
		func(i+1, sum + num[i]);
		func(i+1, sum - num[i]);
	}
	else if (sum == m) count++;
}
 
int main() {
	int i;
	scanf("%d %d", &m, &n);
 
	for (i = 0; i < n; i++) {
		scanf("%d", &num[i]);
	}
 
	func(0, 0);
	printf("%d", count);
}

재귀함수를 사용한 간단한 코드입니다.
이 코드의 func(i+1, sum+num[i])를 했을 때에는 답이 잘 나오지만,
func(i++, sum+num[i])를 하면 테스트 코드를 모두 해결하지 못합니다.

위의 코드에서 i++와 i+1의 차이점이 궁금합니다.
재귀함수 내의 코드에서는 둘이 뭔가 달라지는 것인가요??

라스코니의 이미지

이것은 간단한 문제가 아닙니다.
i++, ++i 모두 인터넷 검색해서 읽어 보시면 되고,
간단한 문제가 아닌 것은 코드 한 줄에서 여러개의 부효과(side-effect)가 일어나기 때문입니다. side-effect도 구글링해서 찾아보시면 되고.

func(i++, sum+num[i])를 본다면 i++는 뭔가가 먼저 실행이 된 후에 i 값이 증가되는 것이기 때문에 i 초기값이 5라고 한다면 절대 func(6, ...)이 되지 않는다는 겁니다. 그것을 원한다면 적어도 func(++i, ....) 로 해야죠.

그러면 func(++i, sum+num[i]) 로 하면 func(i+1, sum + num[i])와 같아 지냐면 그렇지 않다는 겁니다. i가 5라고 한다면 앞 문장은 func(6, sum+num[??])가 되지만 뒷문장은 항상 func(6, sum + num[5])가 된다는 것이죠. 앞의 ??는 어떤 값이 될지 모른다는 겁니다. 컴파일러 차이에 따라서 달라질 수 있습니다.

거두 절미하고 아마(?) 좋은 코드는 어떤 것과 가까울 것이냐면, 원래 쓰인 문장이 가장 좋습니다. 한 문장 내에서 side-effect를 일으킬 수 있는 동작은 주의해서 써야 합니다. i++, ++i가 나쁜게 아닙니다. 매우 같은 쓰는 것이 권장되는 연산자이고, 다만 주의해서 써야 한다는 것이죠.

익명 사용자의 이미지

재귀 호출이 문제가 아닙니다.
문제가 되지 않는 부분을 다 덜어내고 핵심만 남겨봅시다.

int i = 0;
f(i++, i);

함수 f는 어떤 매개변수를 받게 될까요?

1. side effect

C언어에서, 2 + 3은 5로 계산됩니다.
int형 변수 i의 값이 0이었다면, i + 1은 1로 계산됩니다.

그럼 i++은? 0으로 계산됩니다. 그리고 i의 값은 1 증가하여 1이 됩니다.
위 경우처럼 표현식이 평가될 때, 그 값이 계산되는 것 이외에 실행 환경에 변화가 생기는 경우 (e.g., 변수의 값이 바뀌는 등), 이를 side effect라고 합니다.

2. unsequenced

함수 호출 f(i++, i);로 돌아옵시다.
함수의 매개 변수로 전달될 두 개의 부분 표현식이 있습니다. 각각 i++i이죠.

어느 것이 먼저 평가될까요?
보통은 앞의 것이 먼저 평가될 거라고 생각하겠지만, C언어에서 매개변수의 평가 사이에는 선후관계가 없습니다. 이런 걸 unsequenced라고 합니다.

이 경우, 앞의 i++가 먼저 평가될 수도 있고, 뒤의 i가 먼저 평가될 수도 있고, 심지어 뒤섞여서(interleave) 평가될 수도 있습니다.

3. undefined behavior

문제는, 어떤 scala object에 대한 side effect가, 그 scala object의 값을 사용하는 값 계산과 unsequenced일 경우 undefined behavior가 발생한다는 겁니다.

이런 경우에 어떤 일이 일어나게 되는지는 100% 컴파일러 마음대로입니다.

의도한 대로 동작할 수도 있고, 그렇지 않을 수도 있고, 완전히 엉뚱한 결과가 나올 수도 있고, 전혀 일관성이 없을 수도 있어요.

undefined behavior는 C언어로 프로그래밍할 때 반드시 피해야 합니다.

4. 마무리

C언어에서 표현식을 작성할 때, 한 표현식에서 변수의 값을 변화시키면서 동시에 그 변수의 값을 사용하는데, 뭔가 그 사이에 선후관계가 명확하지 않다 싶으면 이런 경우에 걸릴 가능성이 높습니다.

예를 들어 i = ++i + 1; 이런 거.
이런 거 하지 마세요.

5. 추신

예시에서 i++가 아니라 ++i였어도 마찬가지입니다.

익명 사용자의 이미지

마무리에서 든 예시가 잘못됐군요. 정정합니다.
저건 scala object에 대한 두 side effect가 unsequenced 되어 발생한 undefined behavior입니다.

제대로 예시를 들려면 a[i++] = i; 이런 게 좋겠죠.

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.