[완료]재귀함수로 아주 큰값을 다룰 경우에 혹은 너무 재귀를 많이 할 경우

임종규의 이미지

재귀함수로 n까지의 합을 구하는 함수를 만들었습니다.

어느정도 작은값(1만정도)까지는 계산을 하는데 그 이상을 넘으면 계산을 하지(?) 않습니다.
계산을 하다가 에러를 보여주는 것도 아니고 그냥 종료됩니다.

타입을 unsigned long 으로 했다가 숫자가 표현을 못하는거 같아서 찾아보니 __int64 가 있길래 써봤습니다.
그런데 타입을 바꿔봐도 그대로더라구요.

"(1+n)*n/2 로 계산하면 되는데.. "
"큰수를 표현하려면 새로운 타입선언해야 되요"
.... 이런 답변을 원하는 게 아니라

큰수를 입력해보면 main 에서 v, w 를 출력하는 부분에서 큰 수도 다 표현이 됩니다.
그런데....
아래 코드를 실행해 보시면 아시겠지만(어쩌면 제 컴퓨터에서만 안될지도 모르겠습니다.)
입력값으로 100000(십만)을 입력해보면 과정을 출력을 하다가 종료됩니다.(그냥 멈추길래 과정을 보여주도록 고친겁니다.)

재귀함수를 잘못 짠거 같기도 하고... 제가 알고 있는 대로라면 별 문제 없어 보이는데
혹시 다른 분들이 보셨을 때 문제점이 보이시면 알려주셨으면 고맙겠습니다.

#include <stdio.h>
 
//5,000,000,000,000 까지 표현
__int64 foo(__int64 v, __int64 w)
{
	static __int64 count = 0;
	if (v > w)
	{
		return 0;
	}
	else if (v == w)
	{
		return v;
	}
	else
	{
		printf("%I64u : %I64u, %I64u, %I64u\n", count+1, v, w, (count+1)*(v + w));
		count++;
		return v + w + foo(v+1, w-1);
	}
}
 
int main(int argc, char *argv[])
{
	__int64 v, w;
 
	printf("enter : ");
 
	v = 1;
	scanf("%I64u", &w);
 
 
	printf("%I64u - %I64u : \n", v, w);
	printf("%I64u\n", foo(v,w));
 
	return 0;
}

익명 사용자의 이미지

tail recursion 문제인지 체크해보고 맞다면 컴파일러가 tail recursion 지원하는지 체크, 그리고 tail recursion으로 코드 작성해 보세요.

임종규의 이미지

tail recursion이 반환되는 주소를 기억해야 한다는 문제점을 해소한 재귀함수라고 이해했습니다만.. 맞게 이해한거지요...

이해한만큼 고쳐보았습니다만 여전히 실행하다가 종료되어버립니다.(아무래도 잘못 이해한거 같습니다 -_-;;;)

컴파일러는 VC++6.0 입니다. 설정에서는 tail recursion 과 관련된 문구를 찾아 볼수는 없었습니다.

#include <stdio.h>
 
//5,000,000,000,000
void foo(__int64 v, __int64 w, __int64 *sum)
{
    static __int64 count = 0;
    if (v > w)
    {
        return;
    }
    else if (v == w)
    {
        *sum = *sum + v;
    }
    else
    {
        printf("%I64u : %I64u, %I64u, %I64u\n", count+1, v, w, (count+1)*(v + w));
        count++;
        *sum = *sum + v + w;
        foo(v+1, w-1, sum);
    }
}
 
int main(int argc, char *argv[])
{
    __int64 v, w, sum;
 
    printf("enter : ");
 
    sum = 0;
    v = 1;
    scanf("%I64u", &w);
 
 
    printf("%I64u - %I64u : \n", v, w+1);
    foo(v, w, &sum);
    printf("%I64u\n", sum);
 
    return 0;
}

/* How to Love Others */
while(GetDepth(Love) < Enough) DoLove();

/* How to Love Others */
while(GetDepth(Love) < Enough) DoLove();

절차탁마의 이미지

stack overflow일 가능성이 아주 큽니다.

임종규의 이미지

절차탁마님께서 말씀하신대로 stack overflow 라면 어떻게 수정해야 하나요?

위에 답변 다신 익명자께서도 stack overflow 를 해결하는 방법으로 tail recursion을 알아보라고 하신 것 같은데....

고친다고 고친것도 제대로 작동을 하지 않으니 답답하네요

/* How to Love Others */
while(GetDepth(Love) < Enough) DoLove();

/* How to Love Others */
while(GetDepth(Love) < Enough) DoLove();

익명 사용자의 이미지

C 에서는 함수를 한 번 호출할 때마다 함수에서 사용되는 변수들을 위해 메모리 영역을 잡고 "스택" 이라고 부르는 자료구조에 이 영역을 넣습니다. 그런데 이 메모리는 함수가 종료될 때까지 해제 되지 않고 계속해서 쌓여가기 때문에 재귀 호출을 많이 하게 되면 함수가 종료되지 않고 같은 함수를 계속해서 호출하니까 스택으로 사용할 수 있도록 제한된 메모리를 다 써버리게 됩니다. 그래서 프로그램이 멈추는 겁니다. 해결 방법은 스택 사이즈를 늘리거나 재귀 호출을 하지 않도록 프로그램을 고쳐야 합니다. 스택 사이즈를 늘려도 메모리에 한계가 있으므로 재귀호출하는데에는 재한이 있으므로 정말 많은 계산을 해야한다면 재귀 호출을 하지 않도록 프로그램을 고쳐야 합니다. 윗 분이 말씀하신데로 tail recursion (재귀적으로 호출한 뒤 그 반환 값을 가지고 다른 작업을 하지 않고 바로 리턴하는 재귀) 인 경우 항상 재귀 호출을 않도록 고칠 수 있습니다.

절차탁마의 이미지

잘 기억나지는 않지만 tail recurstion은
함수의 끝에서 recursion을 하는 형태 입니다.
질문 하신 내용이 tail recursion일겁니다.

recursion은 일반적으로 보기 어렵고, 속도가
좀 느리고 하는 단점이 있습니다.

그래서 tail recursion은 iteration으로
바꿔서 작성합니다.

임종규의 이미지

iteration 을 사용하지 않고 recusion을 이용해서 해볼려고 했는데 쉽지 않군요....

tail recursion 쪽을 좀 더 찾아봐야 할 것 같네요....

답변 감사합니다.

/* How to Love Others */
while(GetDepth(Love) < Enough) DoLove();

/* How to Love Others */
while(GetDepth(Love) < Enough) DoLove();

익명 사용자의 이미지

tail recursion을 사용하려면 컴파일러에서 지원이 되야 합니다. GCC는 일부 지원되는 것으로 알고 있으나, 정확치 않으니 확인하세요.

tail recursion은 recursion 이지만 컴파일러에 의해 iteration으로 바뀌어 컴파일 되는 것이기 때문에 iteration 버전과 속도가 같습니다.

이도저도 이해가 안된다면 recursion 사용하지 않는 것이 답일 가능성이 큽니다.

임종규의 이미지

tail recursion 이 iteration 으로 변환되지 않는 한 재귀함수는 스택의 크기 때문에 재귀의 횟수에 제한이 있다라고 이해하면 되는건지요?

만약 그렇다고 한다면 컴파일러를 바꿔야 하겠네요...

뭔가 다른게 있지 않을까 생각되지만 일단 컴파일러 바꿔서 실행해보고 제대로 되면 할말이 없는거군요...

iteration 을 사용할 수도 있지만 그냥 recursion 을 사용해보고 싶어서 사용했던 것 뿐입니다.

재미로 시작했는데 생각대로 안되니 왜 안되는지 굉장히 궁금하네요... 알고 있던게 바닥나는 느낌이네요 -_-;;

/* How to Love Others */
while(GetDepth(Love) < Enough) DoLove();

/* How to Love Others */
while(GetDepth(Love) < Enough) DoLove();

절차탁마의 이미지

재귀함수의 횟수에 제한이 있습니다.
그건 컴퓨터의 메모리 한계땜에 어쩔수
없는 부분입니다. 그리고 컴파일러를
바꿔서 해본다는것에는 회의적입니다.

컴파일러에서 optimization level에
따라 tail recursion을 iteration으로
바꿀수는 있지만, tail recursion을
지원하고 않하고 하는 compiler는 없다고
생각합니다. 지원않한다는 애기가
tail recursion이 있으면 syntax error를
내뱉는다는 애기인지, 아니면 iteration으로
바꾸지 않는다는 애기인지 분명치 않네요

recursion 형태가 뭐가 됬든
메모리 제한땜에 function call depth에 한계가
있다고 생각하시면 됩니다. 무한 메모리가
아니거든요!!! recursion이 아니어도
함수 call시 스택잡아먹는거는 똑갑습니다.

결론 : 컴퓨터의 메모리는 유한하다.
그러므로 function call depth도 유한하다.

뱀다리 : stack based system이 아니라면
가능할지도..(아시는 분 있으면
답글 부탁 드립니다^^)

dragonkun의 이미지

recursion 이 아니어도 함수 call 시 스택 잡아먹는 것이 같다고 했는데, 그렇지 않는 걸로 알고 있습니다.
물론 함수가 call 이 될 때 스택에 쌓이는 것은 맞지만, 일반적으로는(recursion 이 아닌 경우) 함수가 종료되면 그 내용이 모두 pop 되어서 문제를 일으킬 여지가 없습니다. recursion 은 함수가 다 끝나기 전에 계속해서 함수를 호출하기 때문에 pop 되지 않고 계속 스택의 내용이 쌓여만가는 거지요.

tail recursion을 지원하는 컴파일러는 recursion 의 function call 을 while loop 으로 변경 해버립니다. 따라서, 스택을 아예 쓰지 않지요. 컴파일러가 tail recursion을 지원하지 않는다면, while loop 으로 변경하는 것이 아니라 일반적인 function call 과 같은 동작을 하겠죠.
function call 에서 왜 스택을 쓸까요? function call 이 이루어지고 난 후에 다시 function call 하기 전의 상태로 만들어야 하기 때문에, 스택을 쓰는 것으로 알고 있습니다. 따라서 function call 이 있기전에 caller 에서(혹은 callee에서) 스택에 쌓아 뒀다가, function call 이 끝나면 그 값을 가져오는 거죠. 하지만 tail recursion 은 function call 하기 전에 저장할 상태가 없고, 따라서 굳이 function call 의 형태가 필요가 없게 되어서 그냥 일반 반복문으로 변경할 수가 있는 거겠지요.

이상 제가 알고 있는 바입니다. 사실 틀릴지도 몰라요. :)
틀린 부분이 있으면 지적해 주세요.
---------
Emerging the World!

Emerging the World!

절차탁마의 이미지

"recursion 이 아니어도 함수 call 시 스택 잡아먹는 것이 같다고 했는데, 그렇지 않는 걸로 알고 있습니다.
물론 함수가 call 이 될 때 스택에 쌓이는 것은 맞지만.."

이거 모순아닌가요?

dragonkun의 이미지

음.. 문장을 매끄럽게 쓰지 못했나 본데;;
그러니까 '잡아먹는다'라는 표현에 애매함이 있다고 봅니다.
recursion 의 경우는 스택을 push, push, push, ..... push, pop, pop, pop pop ,... pop 형태로 쓰게 되는 거고. (이렇게 스택이 줄지 않고 쌓여만 가는 걸 '잡아먹는다'라고 표현한 겁니다.)
아닌 경우는 push, pop, push, pop, push, pop 이런 형태로 쓰게 되는 거죠. depth 가 들어가더라도 recursion 처럼 계속 depth 가 증가하지는 않는다는 이야기입니다. (혹시나 해서 말씀드리는 거지만 a 에서 b 를 호출하고 다시 b 에서 a 를 호출하는 것도 recursion 입니다.)
스택 오버플로우는 너무 많은 push 때문에 한계치에 다달아서 생기는 거구요.

그리고 다시 말해서 결론은 tail recursion의 경우는 컴파일러에 따라서 스택을 쓰지 않을 수가 있고, 그 경우엔 스택에 의해서 횟수가 제한되는 일이 없다는 겁니다.
-----
Emerging the World!

Emerging the World!

절차탁마의 이미지

만약에 a()->b()->c(),...aa()->bb()...->zzzz()...
와 같이 호출한다면 이건 어떻게 되나요?

이건 recursion이 아니어도 depth가 증가 하는게 아닌가요?

recursion이든 아니든 function call이라는 관점에서 차이가 있나요?

dragonkun의 이미지

아.. 이야기를 다시 하죠. function call 부분은 할 필요가 없었는데 괜히 꺼냈군요. 알고 계시는 게 맞습니다.
그냥 어설픈 설명은 다 무시해주세요;;;

tail recursion 은 컴파일러에 따라서 function call로 처리되지 않을 수 있다는게 핵심이 되겠습니다.
tail recursion 은 iteration으로 변환될 수 있고(사실상 이렇게 되면 tail recursion 은 더 이상 recursion이 아니게 되죠.),
모든 recursion 을 tail recursion 으로 변환할 수 있는 것은 아닙니다.

컴파일러에서 지원을 안 하면 일반 재귀로 function call로 처리되구요.
---------
Emerging the World!

Emerging the World!

익명 사용자의 이미지

주장하시고자 하는 요지가 뭔지 분명치는 않지만,
분명한 것은 tail recursion이고 컴파일러가 지원한다면,
사람이 손으로 iteration으로 바꾸듯,
컴파일러가 iteration으로 transform 한다는 겁니다.

보이는 것은 recusive 지만, 실제 프로세스는 iteration이 된다는 겁니다.

서지원의 이미지

tail recursion과 recursion의 차이점은 현재의 stack frame을 재사용할 수 있느냐 아니냐 입니다.
아주 간단하게 factorial함수를 예를 들면,

return n * factorial(n-1) 이라고 하면 tail recursion이 아니지만, return factorial(n * partial_result, n-1) 이라고 하면 tail recursion입니다. 전자와 후자의 차이는 recursive function의 결과를 가지고 어떠한 계산을 하는 경우(전자)에 현재 local variable을 저장하고 있는 stack frame에 있는 정보를 recursive function이 return할 때까지 가지고 있어야 하지만 후자의 경우에는 recursive function이 return하는 내용을 caller가 그대로 return하기 때문에 현재의 stack frame을 recursive function이 쓰도록 optimize할 수 있습니다. 즉,

int factorial(int partial_result, int n) {
if (n==1) return partial_result;
else return factorial(n*partial_result, n-1);
}

이같은 함수는

int factorial(int partial_result, int n) {
next:
if (n==1) return partial_result;
else {
partial_result = n * partial_result;
n = n-1;
goto next;
}
}

이와같이 compiler가 optimize할 수 있습니다.

int factorial(int n) {
if (n==1) return partial_result;
else return n* factorial(n-1);
}

의 경우에는 argument인 n(현재 stack frame에 있음)과 recursive function의 결과를 곱하기 때문에 stack frame을 recursive function이 쓰도록 optimize할 수 없습니다.

임종규의 이미지

이번 기회에 tail recursion 을 알게되었네요.

위에 제가 올렸던 소스를 full optimization 옵션에 favor small code 옵션을 주고 실행해보니까(이게 말씀하신 tail recursion to iteration 변환기능인듯합니다.)
iteration 으로 변환이 되었는지 전에 멈추던 현상은 사라지고
원하는 결과가 나옵니다.

답변 달아주신 모두분들 감사합니다.

많은 공부가 되었습니다. (__)

/* How to Love Others */
while(GetDepth(Love) < Enough) DoLove();

/* How to Love Others */
while(GetDepth(Love) < Enough) DoLove();

댓글 달기

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
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.