재귀호출 프로그램

1anytime의 이미지

자료구죠 접한지 얼마안된 병아리입니다. C로코딩해오라는데 난감하기만 하네요.. 다른분이 코딩한거라도 이해했으면 좋겠습니다.

바쁘시더라도 코드 몇줄 적어주시면 안되나요.

File attachments: 
첨부파일 크기
Image icon ds.JPG33.48 KB
Image icon A.png3.08 KB

댓글

nachnine의 이미지

숙제를 대신해줄 만큼 한가한 사람은 없을텐데요.
재귀호출의 개념에 대해 묻는게 아니라
스캔한 이미지를 그대로 올리는 의도가 궁금하군요.

원하는 답을 주지 않으니 기분이 상하시겠지만.
kldp는 숙제해결사이트가 아닙니다.
그리고 재귀호출에 대해서 나오지 않는 교과서는 없을텐데
책은 보셨는지 궁금하군요.

남의 코드를 보고 이해를 하려는 태도는 좋지만,
스스로 짰을때 이해가 더 확실하고, 얻는 것도 많습니다.

M.W.Park의 이미지

단언컨대, 이렇게 어려운 문제를 풀 수 있는 사람은 여기에 없습니다.
시스템에 꽂혀있는 processor 숫자와 가용한 stack의 byte 수 및 k의 range등이 있어야 guru 등급의 사용자가 쬐끔 관심을 가져줄 것입니다. :twisted:

-----
오늘 의 취미는 끝없는, 끝없는 인내다. 1973 法頂

yui의 이미지

C책에서 재귀호출 부분을 보세요.
아마 피보나치 수열이 예로 나올 텐데 그 코드를 검토해보세요.
한 5줄정도 입니다. 그리 어렵지 않습니다.
꼭 직접 해보세요!

gizrak의 이미지

위에 나온 문제 정말로 별로 어렵지 않은 문제들입니다. 정말로요...

조금만 생각하시면 될겁니다. 다른 재귀함수 프로그램을 분석해보세요.

예를들어,

a(k+1) = a(k) + 1

a(0) = 1

같은 경우는...

int recur(int x)
{
	if(x == 0)
		return 1;
	else
		return recur(x-1) + 1;
}

참고하세요. 참고일뿐... ㅋ

void main(void)
{
char *brain;
brain = malloc(sizeof(stress));

free(brain);
}
뭐든지 답은 간단한데서 시작한다.

nachnine의 이미지

Resursive 함수 만들때 유의 사항중 하나가

함수내의 local variable의 크기가 크면
recursive depth가 약간만 늘어나도 memory를 무지하게 많이
차지하게 된다는 겁니다

뭐 하노이나 단순한 걸 하면 괜찮은데

노드가 많고 Depth 가 큰 TreeTraversal을 하면서
복잡한 문자열 처리를 한다든가 하면 이런부분도 신경써야 합니다.
( 노드 5000개에 max depth 12 정도되는 tree를 recursive 하다가
알게 된거죠 )

void RecurvieF(paramType P){

변수선언
로직처리
RecursiveF(anotherP);

}

가 아니라

void RecurvieF( paramType P){

RecursiveF( anotherP);
변수 동적할당
로직처리
해제

}

처럼 하면 메모리를 훨씬 덜쓰죠

hackexpert의 이미지

3번 문제 간단하게 펄로 한번 해봤습니다..
재귀 한번 얻은값은 변수에 저장하였다가 다음에 꺼내다 씁니다..

아 어제 휴가 냈더니 일이 좋아라 하고 덤비네요.. ㅡ.ㅜ
잠시 막간을 이용해서..
c는 왠지 귀찮아서.. ㅡㅡㅋ

도움 되시길..
그냥 재귀에 대한 문제는 패턴이 다 비슷비슷해서
하나만 이해하셔도 왠만한건 다 될겁니다..

#!/usr/local/bin/perl

use strict;

my @checktable;
my @savetable;

my $k = shift;
&init();
print &recur($k)."\n";

sub init
{
    $checktable[0] = 1;
    $checktable[1] = 1;
    $savetable[0] = 0;
    $savetable[1] = 1;
}

sub recur
{
    my $k = shift;

    return $savetable[$k] if $checktable[$k];

    my $result = 2* &recur($k-1) - &recur($k-2);
    $savetable[$k] = $result;
    $checktable[$k] = 1;
    return $result;
}
dhunter의 이미지

보고 있으니 PHP나 VB로 포팅 :) 하고 싶은 생각이 드는군요.

from bzImage
It's blue paper

envia의 이미지

ocaml ;;

let rec first x = if x == 0 then 1 else first(x - 1) + 2;;
let rec second x = if x == 1 then 1 else 3 * second(x - 1) + 1;;
let rec third x = if x == 0 then 0 else if x == 1 then 1 else 2 * third(x - 1) + third(x - 2);;

----

It is essential, if man is not to be compelled to have recourse, as a last resort, to rebellion against tyranny and oppression, that human rights should be protected by the rule of law.
[Universal Declaration of Human Rights]

choissi의 이미지

왠지.. 다양한 언어의 코드로 댓글이 달릴 듯한
느낌입니다.

울랄라~ 호기심 천국~!!
http://www.ezdoum.com

맹고이의 이미지

(a)번 문제에... '-'가 아니라 '='이 되어야 되는 게 아닌지... (머리가 녹슬어서)

아무튼, f(n) = 2n + 1 이라고 보면...

f = lambda n: 2 * n + 1

해놓고 보니 재귀호출이 아니네요. -_-;

그래서 (b)번 문제... ;;

f = lambda n: (n == 1 and 1) or (n != 0 and f(n - 1) * 3 + 1) or 0

cedar의 이미지

ㅋㅋ... 저도 참가합니다. :wink:

어차피 C++의 template metaprogramming에서는
recursion만 가능하고 iteration은 불가능합니다.

//---------------------------------------------------------------------------

#include <iostream>

template<int k>
struct series_a {
    enum { value = series_a<k - 1>::value + 2 };
};

struct series_a<0> {
    enum { value = 1 };
};
//---------------------------------------------------------------------------

template<int k>
struct series_b {
    enum { value = 3 * series_b<k - 1>::value + 1 };
};

struct series_b<0> {
    enum { value = 1 };
};
//---------------------------------------------------------------------------

template<int k>
struct series_c {
    enum { value = 2 * series_c<k - 1>::value - series_c<k - 2>::value};
};

struct series_c<0> {
    enum { value = 0 };
};

struct series_c<1> {
    enum { value = 1 };
};
//---------------------------------------------------------------------------

int main()
{
    const int k = 10;
    std::cout << series_a<k>::value << std::endl;
    std::cout << series_b<k>::value << std::endl;
    std::cout << series_c<k>::value << std::endl;
    return 0;
}
//---------------------------------------------------------------------------

kall의 이미지

dhunter wrote:
보고 있으니 PHP나 VB로 포팅 :) 하고 싶은 생각이 드는군요.

PHP는 너무 쉽지 않나요? C랑 거의 같아서..
VB는 안써봐서 모르겠군요.

프레드 wrote:

int recur(int x)
{
	if(x == 0)
		return 1;
	else
		return recur(x-1) + 1;
}

function recur($x)
{
	if($x == 0)
		return 1;
	else
		return recur($x-1) + 1;
}

함수 선언 부분 고치고 변수앞에 $만 붙여주면... :)

----
자신을 이길 수 있는자는
무슨짓이든 할수있다..
즉..무서운 넘이란 말이지 ^-_-^
나? 아직 멀었지 ㅠㅠ

envia의 이미지

C @.@

int first(int i){return i?first(i-1)+2:1;}
int second(int i){return --i?3*second(i)+1:1;}
int third(int i){return i<2?2*third(i-1)-third(i-2):i;}

Scheme ^^

(define (first x) (if (= x 0) 1 (+ (first (- x 1)) 2)))
(define (second x) (if (= x 1) 1 (+ (* 3 (second (- x 1))) 1)))
(define (third x) (cond ((= x 0) 0) ((= x 1) 1) (else (- (* 2 (third (- x 1))) (third (- x 2))))))

=3 =33

----

It is essential, if man is not to be compelled to have recourse, as a last resort, to rebellion against tyranny and oppression, that human rights should be protected by the rule of law.
[Universal Declaration of Human Rights]

쿠크다스의 이미지

(a)번은 a0=1이고, 공차는 2인 등차수열.
a[n] = 1 + 2*(n-1) = 2*n + 1, n=0,1,2,...

(b)번은,
a[k+1] + 1/2 = 3(a[k] + 1/2).
b[k] = a[k] + 1/2로 하면,
b[k+1] = 3*b[k], b[1] = 1 + 1/2.
b[n] = (1 + 1/2)*3^(n-1) = (1/2)*3^n, n=1,2,3,...
a[n] = (1/2)*3^n - 1/2, n=1,2,3,....

(c)번은,
a[n+2] - a[n+1] = a[n+1] - a[n].
등차수열임을 알 수 있다.
그리고, 공차 = a[1] - a[0] = 1, 초항 a[0] = 0.
a[n] = n, (n = 0, 1, 2, 3, ...)

과자가 아닙니다.
cuckoo dozen, 즉.12마리의 뻐꾸기란 뜻입니다.

yielding의 이미지

관리자님의 기대에 답하여

[vim script]

function Recur(x)
    if (a:x == 1)
       return 1
    else
        return 1 + Recur(a:x - 1)
endfunction

Life rushes on, we are distracted

nohmad의 이미지

세번째 것은 하다가 막혀서 envia님 소스를 참고했습니다.

python

first  = lambda k: k==0 and 1 or first(k-1)+2
second = lambda k: k==1 and 1 or 3*second(k-1)+1
third  = lambda k: k>1 and 2*third(k-1)-third(k-2) or k

ruby

def first(k) k==0 and 1 or first(k-1)+2 end
def second(k) k==1 and 1 or 3*second(k-1)+1 end
def third(k) k>1 and 2*third(k-1)-third(k-2) or k end
fender의 이미지

자바버전 입니다... 맞는지는 모름... -_-;;; =3

import java.text.MessageFormat;

public class RecursiveCallExample {
    private int a;
    private int b;
    private int c;
    private int a0;

    public RecursiveCallExample(
            final int a,
            final int b,
            final int c,
            final int a0) {
        checkPositiveInteger(a, "a");
        checkPositiveInteger(b, "b");
        checkPositiveInteger(c, "c");
        checkPositiveInteger(a0, "a0");

        this.a = a;
        this.b = b;
        this.c = c;
        this.a0 = a0;
    }

    private static void checkPositiveInteger(
            final int value,
            final String name) {
        if (value < 0) {
            String msg = MessageFormat.format(
                    "Argument '{0}' should be a positive integer.",
                    new String[] {name});
            throw new IllegalArgumentException(msg);
        }
    }

    public double getValue(final int k) {
        double value;
        if (k == 0) {
            value = a0;
        } else {
            checkPositiveInteger(k, "k");
            value = (b * getValue(k - 1) + c) / -a;
        }

        return value;
    }

    public static void main(final String[] args) {
        //Example usage : a(k + 1) - 3a(k) - 1 = 0, k = 10, a0 = 1
        RecursiveCallExample exam = new RecursiveCallExample(1, -3, -1, 1);
        System.out.println(exam.getValue(10));
    }
}

----------------------------
[서명] 그놈 한국 사용자 모임 - 그놈에 대한 모든 것! - 게시판, IRC, 위키, 갤러리 등등...

lkjt의 이미지

저거 재귀 호출로 짜면 시간 오래 걸리지 않나???,,,

비재귀로 짜셔야되요,

Testors의 이미지

GW-BASIC 으로 작성중이었는데 손댄지 10년이 넘는지라 짱구가 안굴러 가는군요.
IF 다음에 블럭도 안되고 GOTO 에 GOSUB 에..
서브루틴은 리턴값도 못넘기고..
뭐 잘 기억도 안나는군요.
한가지 깨닫게 된점은 GW-BASIC 문법은 어셈블리보다 난해하다는 것입니다. -_-

iolo의 이미지

lkjt wrote:
저거 재귀 호출로 짜면 시간 오래 걸리지 않나???,,,

비재귀로 짜셔야되요,


문제가 재귀로 짜라는 건데요-.-;;;;

그리고, 재귀는 느리다는 편견을 버리세요.
그건 재귀를 두 번 죽이는 거예요-o-

----
the smile has left your eyes...

nachnine의 이미지

뭐 짜기 나름이겠죠;;

재귀호출 잘못 사용하는 대표적인 예가

피보나치 수열을 구하는걸 다음과 같이 구현하는거죠

최악의

  int  fibo (  int n  ){
   //  n is greater than zero .It is definition
   // if  ( n <= 0 ) return -1;
    if ( n ==1 || n == 2 ) return 1;
    return  fibo ( n -1 ) + fibo ( n -2 );
 }

f6
f5 f4
f4 f3 f3 f2
f3 f2 f2 f1 f2 f1 f1
f2 f1 f1 f1 f1
f1


스캔된 3번째 문제도, 위의 잘못된 피보나치 재귀함수의 구현
과 같은 이유로 가능한한 재귀로 안하시는게 좋습니다.
( 확실한 이해 없이 사용하다 된통 당하는 것중 하나가 재귀호출입니다.)
레포트에 문제 3을 재귀로 구현했을때
생기는 문제점을 같이 적어 놓으시면 교수님이 좋아하시겠군요

 int fibo ( int n ){
  if ( n == 1 || n == 2 ) return 1; // definition
  int a= 1;
  int b= 1;
  int c;
    for ( int i = 2 ; i < n ; i++ ){
        c = a + b ;
        a= b;
        b= c;
    }
    return c;
 }
hackexpert의 이미지

nachnine wrote:

그리고 스캔된 3번째 문제도, 위의 잘못된 피보나치 재귀함수의 구현
과 같은 이유로 가능한한 재귀로 안하시는게 좋습니다.

음.. 궁금해서 그러는데요..
알고리즘이 잘못 되었다는 것이 아니라
실행시간 문제와 재귀가 너무 깊어지면서 발생할 수 있는 오버플로우 문제를 말씀하시거 맞죠?

말씀하신 문제가 맞다면 재귀를 안써도 되겠지만..
재귀를 하되 한번 구한 값은 따로 저장시켜두었다 리턴해주는 방법을 써도 간단하게 해결 될 것 같습니다 :)

nachnine의 이미지

한번구한값은 저장하면서 써야하는데

보통 recursive로 구현하면서 그렇게 하진 않죠

함수 바깥에서 접근할수 있는 변수를 지정해서 각 recrusion에

대한 결과를 저장해야합니다

그러면 중복된 함수 호출을 막을수 있죠..

구현은 하되, 그 구현이 가질수 있는 문제에 대해서 언급하는 분이 없어서

썼습니다.

feanor의 이미지

Haskell에서는 재귀로 짜도 성능 문제가 없습니다. 컴파일러가 자동으로 한번 구한 값을 저장해 두거든요. (Value-oriented 언어에서는 가장 기본적인 최적화입니다.)

또 tail call 최적화를 하는 Scheme 같은 경우에도 프로그램을 약간만 주의해서 짜면 재귀를 써도 반복문과 공간과 시간면에서 차이 없는 코드가 나옵니다.

재귀가 느리거나 스택 오버플로우 문제가 있는 것은 C와 비슷한 언어에서나 그렇다는 것입니다.

--feanor

nachnine의 이미지

프로그래머가 이것저것

생각하지 않아도 되니, 참 똑똑한 컴파일러네요 ^^

Haskell 한번 공부해봐야겠습니다.

lacovnk의 이미지

feanor wrote:
Haskell에서는 재귀로 짜도 성능 문제가 없습니다. 컴파일러가 자동으로 한번 구한 값을 저장해 두거든요.

컴파일러는 code를 기계어로 번역해주는 잡다한 일들을 맡는 것 아닌가요? 실행단계에서 알수 있는 재귀호출동안의 값들을 저장하는 걸 컴파일러가 해줄수 있는건가요?

차리서의 이미지

fib = 1 : 1 : [ a+b | (a,b) <- zip fib (tail fib) ] http://www.reeseo.net/doc/trans/hastut/functions.php#sect3.4

--
자본주의, 자유민주주의 사회에서는 결국 자유마저 돈으로 사야하나보다.
사줄테니 제발 팔기나 해다오. 아직 내가 "사겠다"고 말하는 동안에 말이다!

feanor의 이미지

lacovnk wrote:

컴파일러는 code를 기계어로 번역해주는 잡다한 일들을 맡는 것 아닌가요? 실행단계에서 알수 있는 재귀호출동안의 값들을 저장하는 걸 컴파일러가 해줄수 있는건가요?

정확히 말하면, 실행시간에 함수값을 계산한 다음에, 같은 계산을 다시 하지 않도록 넘어온 인자 값과 계산 값을 저장해두고, 다음에 불려질 때 이 저장한 결과를 확인하도록 -- 그렇게 코드가 생성됩니다.

저기 위에 펄에서 array를 사용해서 중간 결과값을 저장해 뒀는데, 그것에 해당하는 코드가 자동으로 들어가는 거죠.

(메모리를 많이 먹는다 싶으면 cache를 free하는 코드도 들어갑니다.)

--feanor

lacovnk의 이미지

오오오오오... 무시무시하군요 :shock:

sodomau의 이미지

헐;;
다이나믹 프로그래밍이 필요 없군요 -_-;

M.W.Park의 이미지

recursion 전반:
http://en.wikipedia.org/wiki/Recursion

tail recursion 설명:
http://en.wikipedia.org/wiki/Tail_recursion

tail recursion이 효과적인 이유(예제):
http://en.wikipedia.org/wiki/Lisp_programming_language#Example_programs

각종 언어에서의 fibonacci number 예제들:
http://en.wikipedia.org/wiki/Fibonacci_number_program

-----
오늘 의 취미는 끝없는, 끝없는 인내다. 1973 法頂

advanced의 이미지

feanor wrote:

재귀가 느리거나 스택 오버플로우 문제가 있는 것은 C와 비슷한 언어에서나 그렇다는 것입니다.

--feanor


gcc 도 3.x 버전대 이상부터 tail recursion 을 지원하는걸로 알고 있습니다

C 로 짜도 tail recursion 조건에 맞게 짜면 됩니다

mastercho의 이미지

nachnine wrote:
숙제를 대신해줄 만큼 한가한 사람은 없을텐데요.
재귀호출의 개념에 대해 묻는게 아니라
스캔한 이미지를 그대로 올리는 의도가 궁금하군요.

원하는 답을 주지 않으니 기분이 상하시겠지만.
kldp는 숙제해결사이트가 아닙니다.
그리고 재귀호출에 대해서 나오지 않는 교과서는 없을텐데
책은 보셨는지 궁금하군요.

남의 코드를 보고 이해를 하려는 태도는 좋지만,
스스로 짰을때 이해가 더 확실하고, 얻는 것도 많습니다.

많은분들이 자기 숙제나 놀이쯤으로 다 받아 들이셨나보네요 :)
다른분의 숙제가 아닌 , 글로 이런 내용의 글이 자주 있었으면 재미가 있을

법도 합니다

승자는 자기보다 우월한 사람을 보면 존경심을 갖고 그로부터 배울 점을 찾지만 패자는 자기보다 우월한 사람을 만나면 질투심을 갖고 어디 구멍난 곳이 없는지 찾는다.
- 하비스

puzzlet의 이미지

Befunge로 해 봤습니다. Befunge는 2차원 프로그래밍 언어이며, 언어에 대한 대략적인 설명은 여기서 보실 수 있습니다: http://en.wikipedia.org/wiki/Befunge

1번 문제

01-&>:1+#v_$\ 1+#v_.@
         >:#v_$1v>2+v
        v-1:<
    ^   <    -10<   <

2번 문제
0&>:#v_$\     #v_.@
     >:1-#v_$1v>3*1+v
      v-1:<
  ^   <      0<     <

3번 문제
01-02-&->:0\`#v_\:0\`#v_\2*\-v
              >:1+#v_$ .@
                   >:2 +#v_$0v
                         >:3+#v_$1v
                              >1+: 1+v
        ^             <      <    <  <

아래 그림파일은 각각의 소스코드의 visualization입니다.

P.S. 3번 문제를 풀 수 있게 도와주신 토끼군 님에게 감사드립니다. :)

댓글 첨부 파일: 
첨부파일 크기
Image icon 88 KB

발발다빠따반반나다발딸발발다빠따따맣발발다뿌
멓터벅더떠벋떠벌더벌벌떠벌떠더법벍떠더벌벌떠

랜덤여신의 이미지

MoniWiki 로 해 봤습니다.

페이지 'Recursive'
#redirect Recursive
카二리의 이미지

proc first { x } {
        if { $x == 0 } {
                return 1
        } else {
                return [expr [first [expr $x-1]]+2]
        }
}

proc second { x } {
        if { $x == 1 } {
                return 1
        } else {
                return [expr 3*[second [expr $x-1]]+1]
        }
}

proc three { x } {
        if { $x < 2 } {
                return $x
        } else {
                return [ expr 2*[three [expr $x-1]]-[three [expr $x-2]] ]
        }
}

TCL 입니다 -.,- TCL 만세~
윈도우에서 GUI 만들기 가장 빠른 TCL TK~! 많이 싸랑좀 해주세요~!

새 생각 :)

cdpark의 이미지

define a(k) {
  if (k == 0)
      return 1;
  return a(k-1)+2;
}

bc script입니다. 제일 쉬운 듯. :)

hjlee의 이미지

feanor wrote:
Haskell에서는 재귀로 짜도 성능 문제가 없습니다. 컴파일러가 자동으로 한번 구한 값을 저장해 두거든요. (Value-oriented 언어에서는 가장 기본적인 최적화입니다.)

또 tail call 최적화를 하는 Scheme 같은 경우에도 프로그램을 약간만 주의해서 짜면 재귀를 써도 반복문과 공간과 시간면에서 차이 없는 코드가 나옵니다.

재귀가 느리거나 스택 오버플로우 문제가 있는 것은 C와 비슷한 언어에서나 그렇다는 것입니다.

--feanor

잘못된 정보이거나 너무 간단히 쓰신 것 같군요.

fib.hs

fib 0 = 0
fib 1 = 1
fib n = fib(n-1) + fib(n-2)

main = do putStr ((show (fib 35)) ++ "\n")

그냥 단순히 위와 같은 haskell code 를 작성하고 실행시켜보면,

O(n) 이 아님을 알 수 있습니다.

$ ghc fib.hs
$ time ./a.out
9227465

real    0m8.724s
user    0m8.252s
sys     0m0.012s

함수 결과 값을 cache하라는 선언이 가능한지, compiler option 이 있는지는 모르나,

위처럼 Fibonacci 수열을 단순하게 작성하고 compile 하면 알아서 값을 cache하는 것 같지는 않습니다.

Lazy evaluation 을 이용한 구현-

fibs = 0 : 1 : (zipWith (+) fibs (tail fibs))

fib n = fibs !! n

코드 출처 -
http://en.wikibooks.org/wiki/Programming:Haskell_overview
(아직 Overview 와 Beginning .. 밖에 없습니다.. :( )

doogle의 이미지

function first(k: integer): integer
begin
  if k = 0 then result:= 1
  else result:= first(k - 1) + 2; // 델파이(오브젝트파스칼) 코드 ^^;;
end;

역시 파스칼은 코딩량이 많죠 ^^;;
음냐.. C/C++ 코딩 안해본지 1년은 넘은거 같네요..
Bini의 이미지

Haskell 

fib 0 = 0 
fib 1 = 1 
fib n = fib(n-1) + fib(n-2) 
main = do putStr ((show (fib 35)) ++ "\n") // fib 40


Clean

fib 0 = 0
fib 1 = 1
fib n = fib(n-1) + fib(n-2)
Start = fib 35 //fib 40

윈도우환경에서 cygwin에 포함된 time 으로 간단히 테스트해봤읍니다

fib35일때는
ghc ---> 0.00user 0.00system 0:08.41elasped 0%CPU...
clean ---> 0.00user 0.00system 0:00.35elasped 0%CPU...

fib40일때는
ghc ---> 0.00user 0.00system 1:34.10elasped 0%CPU...
clean ---> 0.00user 0.00system 0:02.98elasped 0%CPU...

정말 이상하네요?
뭔가 다른 최적화 컴파일옵션이 ghc에 있는건지???

hjlee의 이미지

Bini wrote:
Haskell 

fib 0 = 0 
fib 1 = 1 
fib n = fib(n-1) + fib(n-2) 
main = do putStr ((show (fib 35)) ++ "\n") // fib 40


Clean

fib 0 = 0
fib 1 = 1
fib n = fib(n-1) + fib(n-2)
Start = fib 35 //fib 40

윈도우환경에서 cygwin에 포함된 time 으로 간단히 테스트해봤읍니다

fib35일때는
ghc ---> 0.00user 0.00system 0:08.41elasped 0%CPU...
clean ---> 0.00user 0.00system 0:00.35elasped 0%CPU...

fib40일때는
ghc ---> 0.00user 0.00system 1:34.10elasped 0%CPU...
clean ---> 0.00user 0.00system 0:02.98elasped 0%CPU...

정말 이상하네요?
뭔가 다른 최적화 컴파일옵션이 ghc에 있는건지???

Haskell 의 경우 기본으로 arbitrary precision integer 가 사용되어집니다.
Clean 은 그렇지 않은 것 같구요. (추측입니다.) 32bit integer 가 사용되어진 것이 아닌가 싶군요.

기본 수행 시간의 차이가 클 뿐이지 Clean 도 Haskell 과 같은 형태로 수행되어 지는 것입니다.

제 PC 에서
Clean 의 경우
40 - 2.885
41 - 4.639
42 - 7.442
초가 걸립니다.

n 이 1 증가할 때 대략 1.6 배 수행시간이 더 걸렸습니다.
Clean 도 O(exp n) 이라는 것이지요.

thedee의 이미지

헤스켈이나 클린 코드를 짤 줄 몰라서 리스프로 작성해서 테스트해 봤습니다.

CL-USER 1 > (defun fibo (n) 
              (labels
                  ((fibo-aux (n a b)
                     (if (= n 0)
                         a
                       (fibo-aux (- n 1) b (+ a b)))))
                (fibo-aux n 0 1)))
FIBO

다음은 측정 결과입니다. 출력값이 너무 크기 때문에 실행 시간만 올립니다.

CL-USER 4 > (time (fibo 30000))
Timing the evaluation of (FIBO 30000)

user time    =      1.141
system time  =      0.000
Elapsed time =   0:00:01
Allocation   = 40406208 bytes standard / 5610 bytes conses
0 Page faults
Calls to %EVAL    34

CL-USER 5 > (time (fibo 40000))
Timing the evaluation of (FIBO 40000)

user time    =      1.652
system time  =      0.000
Elapsed time =   0:00:02
Allocation   = 71591800 bytes standard / 2497 bytes conses
0 Page faults
Calls to %EVAL    34

앞서의 헤스켈이나 클린 코드는 테일 리커시브한 코드가 아닙니다. 테일 리커시브하게 사람이 손으로 소스를 수정해 주어야 합니다.

hjlee의 이미지

thedee wrote:

(중략)

앞서의 헤스켈이나 클린 코드는 테일 리커시브한 코드가 아닙니다. 테일 리커시브하게 사람이 손으로 소스를 수정해 주어야 합니다.

:)

예, 그걸 몰라서 그런 것이 아니라,
앞의 페이지를 보시면 아시겠지만 한 분이 Haskell 로 재귀를 짜면 값을 알아서 저장하는 코드를 만들어 준다고 했었습니다.

아무래도 그럴 리는 없을 것 같아서 테스트 해 보았는데, 역시 그냥 짜면 안되더라는 것입니다.

의문이 남아 있는 것은 lisp 의 memoization library 처럼 지정할 수 있느냐, 혹은 비슷한 library 가 있느냐 하는 것이죠.

ftp://ftp.cs.umbc.edu/pub/Memoization/

(require :memoization)

(defun fib (n)
  (if (< n 2) 1
      (+ (fib (- n 2)) (fib (1- n)))))

(memoization:memoize 'fib)

$ lisp
CMU Common Lisp
....
* (load "memoize_test")
* (time (fib 50000))
...
; Evaluation took:
;   3.77 seconds of real time
;   1.971701 seconds of user run time
;   0.772883 seconds of system run time
;   8,265,849,774 CPU cycles
;   [Run times include 1.53 seconds GC run time]
;   0 page faults and
;   122,231,536 bytes consed.
(결과 생략)

* (time (fib 49000))
; Compiling LAMBDA NIL:
; Compiling Top-Level Form:

; Evaluation took:
;   0.0 seconds of real time
;   0.0 seconds of user run time
;   0.0 seconds of system run time
;   19,116 CPU cycles
;   0 page faults and
;   72 bytes consed.
(결과 생략)

* (time (fib 50000))
; Evaluation took:
;   0.0 seconds of real time
;   0.0 seconds of user run time
;   0.0 seconds of system run time
;   19,688 CPU cycles
;   0 page faults and
;   72 bytes consed.
(결과 생략)

cleol의 이미지

fibs = 0 : 1 : (zipWith (+) fibs (tail fibs)) 

fib n = fibs !! n 

fib 0 = 0 
fib 1 = 1 
fib n = fib(n-1) + fib(n-2) 

첫번째 코드가 두번째 코드보다 효율적인 이유가 뭐지요..? haskell(뿐만 아니라 함수형 언어를) 을 접한지 얼마 안된 초보인데...잘 이해가 안됩니다. 어차피 zipWith 역시 재귀로 구현되어있는것 같은데 리스트에 적용을 했다고해서 더 빨라지는 이유가 있나요?

Bini의 이미지

cleol wrote:
fibs = 0 : 1 : (zipWith (+) fibs (tail fibs)) 

fib n = fibs !! n 

fib 0 = 0 
fib 1 = 1 
fib n = fib(n-1) + fib(n-2) 

첫번째 코드가 두번째 코드보다 효율적인 이유가 뭐지요..? haskell(뿐만 아니라 함수형 언어를) 을 접한지 얼마 안된 초보인데...잘 이해가 안됩니다. 어차피 zipWith 역시 재귀로 구현되어있는것 같은데 리스트에 적용을 했다고해서 더 빨라지는 이유가 있나요?

Haskell은 잘 모릅니다만,
비슷한 언어인 Clean 에서는 함수의 패턴매칭은 순수 Lazy evaluation으로 평가한다고 하네요. 그래서 느리다고 하는데...
저도 순전히 취미삼아서 하는언어라... 좀 이해하기가 힘드네요.
아무튼 아래의 코드 1보다는 2가 효율면에서 더 뛰어납니다.
아마 Haskell컴파일러도 비슷하지 않을까 싶은데...

1>
fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
=> Lazy evaluation & recursive

2>
fib :: Int -> Int
fib n
   | n == 0        = 0
   | n == 1        = 1
   | otherwise   = fib (n-1) + fib (n-2)
=> Strict evaluation & recursive

3>
fib :: Int -> Int
fib n = fib` 1 0 1
where
   fib` :: Int Int Int -> Int
   fib` n` l r
      | n` == n        = r
      | otherwise     = fib` (n`+1)  r  (l+r)
=> Strict evaluation & non-recursive

1 < 2 < 3

LispM의 이미지

Daniel Lee wrote:

...
의문이 남아 있는 것은 lisp 의 memoization library 처럼 지정할 수 있느냐, 혹은 비슷한 library 가 있느냐 하는 것이죠.

ftp://ftp.cs.umbc.edu/pub/Memoization/

(require :memoization)

(defun fib (n)
  (if (< n 2) 1
      (+ (fib (- n 2)) (fib (1- n)))))

(memoization:memoize 'fib)

...

CL에서는 사실 위와같이 할 필요도 없이 매크로를 사용하여

(define-memo-function fib (n)
  (if (< n 2) 1
      (+ (fib (- n 2)) (fib (1- n)))))

이렇게 해서 memoization을 사용할 수 있습니다. 매크로가 익스팬드 되고 나면 위와 같은 일을 하겠죠.
그런데, 위의 링크는 이미 존재하지 않고 웹상에 있는 Marty Hall의 memoization에는 버그가 있습니다(사실 리습 프로그래머는 거의 누구나 memoization에 대해 알기 때문에 고쳐서 사용하거나 스스로 작성해서 쓰는데 큰 문제는 없습니다)

http://lisp.or.kr http://lisp.kldp.org - 한국 리습 사용자 모임

sliver의 이미지

cleol wrote:
fibs = 0 : 1 : (zipWith (+) fibs (tail fibs)) 

fib n = fibs !! n 

fib 0 = 0 
fib 1 = 1 
fib n = fib(n-1) + fib(n-2) 

첫번째 코드가 두번째 코드보다 효율적인 이유가 뭐지요..? haskell(뿐만 아니라 함수형 언어를) 을 접한지 얼마 안된 초보인데...잘 이해가 안됩니다. 어차피 zipWith 역시 재귀로 구현되어있는것 같은데 리스트에 적용을 했다고해서 더 빨라지는 이유가 있나요?


Haskell에서는 (아마도 정확히는 일반적인 haskell구현에서는) 최대한 이미 계산된 값을 공유하기 때문입니다.
fibs의 정의에서 (tail fibs)를 얻기 위해 fibs를 다시 처음부터 계산해 내는 대신에 이미 지금까지 계산된 fibs를 이용함으로써 마치 iterative한 방법으로 fibs를 생성해 내는 효과를 얻을 수 있습니다. 따라서 시간복잡도가 O(n)이 되는 것이죠.
그러면 두번째 방법에서도 지금까지 계산된 모든 fib x에 대해 값을 기억해 놓고 나중에 가져다 쓴다면 마찬가지 아니냐...라고 생각하실 수도 있는데, 저도 명확히는 모르지만 일반적으로 함수의 결과값에 대해서는 그런 테크닉을 사용하지 않는 듯 합니다.
만약 값을 공유하는(?) 테크닉을 전혀 사용하지 않는 (무식한) haskell구현이 있다면 시간복잡도는 두 방법 모두 O(2^n)으로 같을 겁니다.
정재윤의 이미지

Quote:

Haskell은 잘 모릅니다만,
비슷한 언어인 Clean 에서는 함수의 패턴매칭은 순수 Lazy evaluation으로 평가한다고 하네요. 그래서 느리다고 하는데...
저도 순전히 취미삼아서 하는언어라... 좀 이해하기가 힘드네요.
아무튼 아래의 코드 1보다는 2가 효율면에서 더 뛰어납니다.
아마 Haskell컴파일러도 비슷하지 않을까 싶은데...

하략...

일단 위의 코드가 빨라지는 것은 dynamic programming기법에 의한 결과가 맞습니다. 예로 설명하시는 것은 lazy evaluation language에서 pattern matching이 흔히 lazy하게 이루어 지기 때문입니다. 이를 2처름 strict하게 만들면 효율면에서 좋아집니다. 하지만 표현력이 떨어지게 됩니다. 하지만, 대부분의 컴파일러들이 strict analysis라는 분석을 해주기 때문에 이 정도에서 큰 득을 보기는 어려울 겁니다.

Bini의 이미지

참 너무도 한심한 답변이라.....
저 위에 것도 지워버리고 싶군요.....
코드를 다시 자세히 읽어보니 너무 당연한 결과인데 전혀 엉뚱한 말만 늘어놓고 있었네요.....
이놈의 덜렁거림을 언제나 고칠런지.....

violino의 이미지

doogle wrote:
function first(k: integer): integer
begin
  if k = 0 then result:= 1
  else result:= first(k - 1) + 2; // 델파이(오브젝트파스칼) 코드 ^^;;
end;

역시 파스칼은 코딩량이 많죠 ^^;;
음냐.. C/C++ 코딩 안해본지 1년은 넘은거 같네요..

표준(안시) 파스칼 코드 같은데요?
마지막 end 앞에 있는 ; 만 빼면요.
(요즘 그거 갖고 불평하는 파스칼 컴파일러는 거의 없겠죠 ^^)

JWC의 이미지

잘 배워 갑니다 :wink:

puzzlet의 이미지

Mathematica입니다. 문제 그림이 깨져 있는데, 원래 문제를 잘 복원해서 나타내 줄 수 있는 언어라고 생각합니다.

a1[x_] := a1[x-1] + 2
a1[0] := 1

a2[x_] := 3 a2[x-1] + 1
a2[1] := 1

a3[x_] := 2 a3[x-1] + a3[x-2]
a3[0] = 0
a3[1] = 1

발발다빠따반반나다발딸발발다빠따따맣발발다뿌
멓터벅더떠벋떠벌더벌벌떠벌떠더법벍떠더벌벌떠

ecstatic의 이미지

http://kldp.org/node/34156

죄송합니다.. 썰렁한 개그..

goverment issue

댓글 달기

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