Recursive Function

자기자신을 호출하도록 설계된 함수. "재귀함수"라고 번역된다. 마치 거울 맞은 편에 거울을 놓음으로써, 그안에 사물이 무한개가 되는것과 같은 느낌이고, GoedelEscherBach에서 보여지는 것처럼 비디오카메라로 그 카메라와 연결되어 있는 TV를 실시간으로 찍는 장면을 그 TV로 보는것과 같다.

가장 흔한 예로 factorial 함수 계산 방법이 있다. 페이지 맨 아래에 언어별 구현 코드가 있다.

a! = { 1 if a=1
     { a * (a-1)! if a>1
 * 단, a는 자연수. *

위 계산방법은 신기하게도 잘돌아가고, 성능도 좋다. 잘못쓰면 무한루프에 빠진다. 적절히 끝내는 포인트를 설정해야한다.

RecursiveFunction은 생각하기 편하다는 장점이 있으나 함수가 종료되지 않은 상태에서 반복호출됨에 따라 stack의 메모리를 과다하게 사용하는 문제점이 있다. 함수가 한번 호출되는데 100byte를 사용하고 함수가 10000번 반복 호출된다면, 1MB의 메모리를 사용하게 된다. 그러나 이것을 Recursive하지 않게 해결하면, 수백byte 정도의 메모리를 사용하고 결과를 얻을 수 있는 경우가 많다. 그러나, Tail Recursion일 경우에는 동일 스택에서 실행이 가능하기에 메모리 문제가 없다 -- 효율도 높으면서 동시에 훨씬 단순한 경우가 많다.
see

TailCallOptimization

최근에는 함수콜시 스택사용량도 최적화되어 일반적인 경우 메모리 문제가 크게 문제되진 않는다. (PrologLanguage에서 십만여번의 콜이 있은 후 스택 오버플로우가 났다) 이론학문적으로는 효율이 그다지 중요하지 않은 경우가 많으므로 메모리 문제를 신경쓸 필요가 없고, 필드에서는 데이타의 크기에 따라 콜의 횟수가 달라지는 환경에서 RecursiveFunction을 사용하는 것은 지나치게 위험하므로 잘 사용되지 않는다.(CppLanguage로 상용 서버 프로그램을 짤 때 학교에서 배운 습관대로 list를 RecursiveFunction으로 순회했다가 6번만에 세그멘테이션 폴트가 났다. -_-;) TailRecursion 역시 유연성을 떨어뜨리고 무심코 약간의 수정을 했다가 망가지기 쉽기 때문에 실용적으로 활용하길 원한다면 TailRecursion보다는 Iterative한 방법으로 구현하는 것이 좋다. (실제로 TailRecursion은 Iterative하게 바꾸는 것이 어렵지 않다)

위에서 일어난 현상은 버그를 발견했을 때 그것을 고치지 않고 잠시 땜빵으로 생각을 바꾸어 코딩 하는 것입니다. 인터프리터였다면 세그먼테이션 폴트를 내지 말고 스택 오버플로우 에러를 내야 하고, 컴파일러였다면 제대로 컴파일 해서 세그먼트 폴트를 내지 말았어야 합니다. 프로그래머로써 그때 그때마다 최선의 선택을 해야 하는데, 위와 같은 버그로 인해서 선택의 폭이 좁아져서는 안된다고 생각합니다. 결국 버그가 있는 인터프리터를 고치거나 컴파일러가 컴파일을 제대로 컴파일 하도록, 즉, TailRecursion을 단순 반복으로 컴파일하도록 고쳐야 합니다. 코드는 사람에게는 읽기 쉽게, 컴퓨터에서는 이상없이 작동 되야 합니다. 제 경우에는 필요에 따라 Recursion도 쓰고, TailRecursion도 쓰고, Loop도 사용합니다. 다행히 제가 사용하는 컴파일러는 이 모두를 지원해 주거든요. 필요할 때 사용할 수 있는 자유를 포기하지 마시기 바랍니다. 원래 의도를 잘 표현하지 못한것 같아서 다시 길게 씁니다 --LispM

될 수 있으면 이런 쓰레드모드에선 기존 스레드를 고치시는 것 보다는 아래에 부연 설명을 더 다시는 것이 좋을 것 같네요. 댓글과 앞뒤가 맞지 않게 될 위험이 있으니까요. --Sequoia

생각을 바꾸지 않았습니다.

생각을 한다리 건너서 코딩했을 뿐이죠. TailRecursion의 문제는 SE적 차원에서 볼 때 (원래의 소스를 코딩하지 않은) 개발자의 약간의 수정만으로도 엄청난 결과 - 더이상 TailRecursion이 아니게 되면! - 를 초래할 수 있기 때문에 실용적으로 사용하려면 많은 비용이 따른다는 것입니다. 차라리 처음 코딩할 때 TailRecursion을 Iterative한 버전으로 옮겨쓰는 것이 더 나을 수 있습니다. 그렇게 하는 데에 큰 비용이 든다거나 어려운 테크닉이 필요한 것도 아니고, 그렇게 해도 대부분의 경우 코드를 읽기가 더 어려워지지 않고, 마음 편하게 수정할 수 있지요. 무엇보다도, 찾기어려운오류가 날 확률이 적습니다. TailRecursion은 본질적으로 Iterative한 알고리즘과 같다는 이론적인 의미 이상으로 실용적인 의미를 두기 어려울 것 같네요.

Scheme언어에서 프로그래밍을 한다면 TailRecursion을 쓰면서 두려움에 벌벌 떨지 않아도 된다.언어 차원에서 TailRecursion을 적절히 처리하기 때문이다. 참고로, TailRecursion으로 작성한 무한호출함수를 48시간동안 돌려도 컴퓨터가 맛이 간 일은 없었다. 그러나 Recursive프로세스 방식의 RecursiveFunction은 다른 언어와 마찬가지로 시간이 갈수록 메모리를 잡아 먹는다.

Lisp계열 언어에서는 TailRecursion을 쓰면 알아서 iterative한 코드를 생성해준다고 하네요.

100% 맞는 말은 아닙니다. Scheme의 경우엔 언어 스펙에 TailRecursion을 지원해야 한다고 되어있지만, 가장 현대적인 Lisp 표준인 CommonLisp 스펙에는 그런 말이 없습니다. 하지만 다행히도 대부분의 CommonLisp 구현들은 TailRecursion을 지원합니다.

그 외에 사용된 알고리즘.

DynamicProgramming

[edit]

언어별 Factorial 계산 코드 ¶

파이썬 code

def factorial(num):
    if num == 1:
        return 1
    else:
        return num * factorial(num-1)

CommonLisp code

;;; Rewrote to Lispy style :-)
(defun fact (num)
  (if (= num 1)
      1
      (* num (fact (- num 1)))))

(fact 5)
=> 120

;;; Tail recursion version - Real Lispers will use this style.
;;;
;;; Smart Lisp compiler will produce iterative version of machine
;;; code of this recursive function. Also it may compute even with
;;; a big number.

(defun fact (num)
  (labels ((tail-fact (num result)
              (if (= num 1)
                  result
                  (tail-fact (1- num) (* num result)))))
    (tail-fact num 1)))

PerlLanguage code

sub factorial
{
    my $num = shift;
    if ( $num == 1 ) {
        return 1;
    } else {
        return $num * factorial($num-1);
    }
}

CLanguage code

int fact(int n)
{
  return n ? n * fact(n - 1) : 1;
}

PrologLanguage code

factorial(1,1) :- !.
factorial(Input, Output) :-
 Input2 is Input - 1,
 factorial(Input2, Output2),
 Output is Input * Output2.

MathematicaLanguage code

(* MathematicaLanguage는 기본적으로 팩토리얼 함수로써 n!를 제공한다. 하지만 이를 사용자 함수로서 정의하려면, *)
Factorial[1] = 1
Factorial[i_Integer?Positive] := i * Factorial[i-1]

(* 그리고 List 데이터 형식을 사용하여 RecursiveFunction을 사용하지 않을 수 있다. *)
Factorial[i_Integer?Positive] := Apply[Times, Range[i]]
(* 위 코드를 줄이면 *)
Factorial[i_Integer?Positive] := Times@@Range[i]

Ruby code

#!/usr/bin/env ruby

## iteration version.
module Enumerable
 def product
  self.inject do |i, sum|
   sum *= i
  end
 end
end

def fact(n)
 if n < 2 then
  1
 else
  (1..n).product
 end
end

puts "3! = #{fact(3)}"

## recursive version
def fact_r(n)
 if n < 2 then
  1
 else
  n * (fact n-1)
 end
end

puts "3! = #{fact_r(3)}"

-- -- ageldama 2007-01-16 13:12:17

WikiWiki code
{{|
See RecursiveFunction.

|}}

But where's an exit condition? Stack overflow is likely to occur in my brain --jania

{{|잘못쓰면 무한루프에 빠진다. 적절히 끝내는 포인트를 설정해야한다.|}} 피곤해지면 해결됩니다.

--musiki

Seems human reasoning is about to reach the infinity

--PuzzletChung

J code

   !5                     NB. 팩토리알 동사가 이미 정의되어 있다
120
   */@:>:@i. 5            NB. 0부터 4까지 숫자를 만들어서 각각에 1씩 더한 다음 서로 곱한다
120
   (* $:@<:)`1:@.(0&=) 5  NB. RecursiveFunction. $:는 함수 자신을 가리킨다
120

컴퓨터분류 수학분류