재귀호출 프로그램

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

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);
변수 동적할당
로직처리
해제

}

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

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

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

ㅋㅋ... 저도 참가합니다. :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;
}
//---------------------------------------------------------------------------

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

관리자님의 기대에 답하여

[vim script]

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

자바버전 입니다... 맞는지는 모름... -_-;;; =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));
    }
}

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

뭐 짜기 나름이겠죠;;

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

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

최악의

  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;
 }

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

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

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

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

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

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

썼습니다.

프로그래머가 이것저것

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

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

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

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

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

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

법도 합니다

MoniWiki 로 해 봤습니다.

페이지 'Recursive'
#redirect Recursive

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

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

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

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) 이라는 것이지요.

:)

예, 그걸 몰라서 그런 것이 아니라,
앞의 페이지를 보시면 아시겠지만 한 분이 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.
(결과 생략)

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

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

잘 배워 갑니다 :wink: