재귀 기능 모범 사례; 그들은 무엇인가?

StackOverflow https://stackoverflow.com/questions/1527354

문제

다른 언어는 일반적인 것 이외의 재귀 기능을 설계하는 독립적 인 방법입니다.

if (counter < 1) 
    return output;
else
   callSelf();

다른 방법이 존재합니까? 예제를 볼 때마다 나는 항상 위의 코드 버전을 볼 수 있습니다.

감사! :)

도움이 되었습니까?

해결책

게으른 프로그래밍 언어에서는 엔드 포인트를 정의하지 않는 재귀를 가질 수 있습니다. 결과는 무한한 데이터 구조 일 수 있지만 모든 것을 사용하려고하지 않는 한 괜찮습니다. 예를 들어, Haskell에서 전체 Fibonacci 시리즈를 정의하는 일반적인 방법은 다음과 같습니다.

fibS = 1:1: zipWith (+) fibS (tail fibS)

이것은 다음 영어로 번역됩니다. Fibonacci 시리즈는 1이고 1은 1, 그리고 첫 번째 요소가없는 Fibonacci 시리즈의 요소 별 합계 인 시리즈가 이어집니다.

이것은 재귀 함수 호출보다는 재귀 적 정의처럼 들리지만 하스켈에는 큰 차이가 없습니다. 위의 것은 단지 '무효 함수'(논증이없는 것)입니다.

일반적으로 이것을 사용하려면 FIB의 첫 번째 N 요소 만 사용합니다. 당신은 실제로 당신의 프로그램이 영원히 실행되는 것에 만족하는 한, 모든 것을 모두 사용할 수 있습니다 (예 : 모든 것을 인쇄) :-)

무한 재귀의 '모두'를 사용하는보다 유용한 예를 보려면 웹 서버는 종료되지 않는 재귀 함수를 사용하여 영원히 정의되는 '기본 루프'를 가질 수 있습니다.

편집 : '게으름'의 일부 요소가있는 경우 이러한 원칙은 다른 언어에 확실히 적용될 수 있습니다. 다음은 발전기를 사용하여 Python에 포팅 된 FIB의 위 구현입니다.

def zipWith(func, iter1, iter2):
    while True:
        yield func(iter1.next(), iter2.next())

def tail(iter):
    iter.next()
    for x in iter:
        yield x

def fibS():
    yield 1
    yield 1
    for x in zipWith(lambda x,y: x + y, fibS(), tail(fibS())):
        yield x

# Test it by printing out the first n elements.
def take(n, iter):
    while n > 0:
        yield iter.next()
        n = n - 1

print list(take(10, fibS()))

Haskell 버전만큼 효율적이라고 기대하지 마십시오! 어떤 종류의 해킹과 글로벌 대상을 사용하여 더 효율적으로 만들 수 있습니다. 그러나 명시적인 종료 조건의 부족을 확인하십시오.

다른 팁

그것은 거의 그것입니다.

재귀 기능 설계는 "값을 반환 할 수 있습니까? 아니면 추가 처리를해야합니까?" 그리고 "처리는 그것으로 가치를 반환했습니다. 전달하기 전에 어떻게해야합니까?"

Tail Recursion은 컴파일러/통역사가 성능을 향상시키는 데 사용할 수있는 최적화 방법 일뿐입니다. 기본적으로 재귀 함수가 엄격한 형식을 따르는 경우 (재귀 호출 후에는 아무런 일이 발생하지 않으며, 일반적으로 재귀 호출은 항상 return) 재귀 함수는 최적화 및 루프로 다시 작성 될 수 있습니다.

당신의 질문은 정확히 무엇입니까? 그냥 답을 시도하는 것 ;-)

재귀 유형은 여러 가지가 있습니다.

  • "표준"재귀

    let rec sum = function
    | [] -> 0
    | x::x' -> x + sum x'

  • 꼬리 재귀

    let rec sum acc = function
    | [] -> acc
    | x::x' -> sum (x + acc) x'

  • 상호 재귀

     let rec f() = g()
 and g() = f()

  • 고정점 재귀

    let factorial n = fix(fun rec n -> if n < 1 then 1 else n * rec (n - 1)) n

그리고 재귀 응용 프로그램 목록은 매우 풍부합니다. 기능 프로그래밍에서 모든 반복 코드 (루프 등)는 재귀를 통해 표현됩니다!

또 다른 좋은 예 :

let rec sumTree = function
| End -> 0
| Node(val, right, left) = val + sumTree right + sumTree left

재귀의 주요 "최고 실습"은 종료 조건이 어느 시점에서 만족되도록하는 것입니다. 따라서 초기 호출보다 "작은"데이터를 사용하여 기능을 자체적으로 액자 할 수 있습니다 (트리의 한 부분 만 ). 다른 모든 것은 끝없는 재귀를 초래할 수 있습니다.

글쎄, 당신은 필요합니다 약간 언제 재귀를 중지 해야하는지 아는 방법. 그것이 당신의 것입니다 counter < 1 맞다? 나는 자주 목록에 항목을 제거 / 추가하고, 나무를 가로 지르고, 재발하는 동안 수학적 기능을 수행합니다. 궁극적으로, 당신은 언제 재발을 멈추지 말아야하는지 알아야한다. counter < 1.

function ProcessNode(node)
  //Do stuff
  while (node.Next != null)
    ProcessNode(node.Next);

function ManipulateList(list)
  //Do stuff, adding and removing items based on logic
  if (testCondition)
    return;
  else
    ManipulateList(list);

Google에는 많은 정보가 있습니다 재귀. :)

예를 들어 많은 변형이 있습니다.

foreach (child in parameter.GetChildren()) {
   callself(child)
}

또는

switch (param.length) {
   case 1: return param[0];
   case 2: return param[0] + param[1];
   default: return callself(param.FirstHalf()) + callself(param.LastHalf());
}

그들이 공통적으로 가지고있는 것은 작업을 더 작은 작업으로 삼은 다음 작은 작업을 너무 작아서 사소한 작업으로 해결할 수있을 때까지 작은 작업을 해결하기 위해 스스로를 사용한다는 것입니다.

재귀를 멈추기를 원한다면 테스트를해야합니다.

그러나 하노이 타워 알고리즘 (2 재귀 호출)과 같이 약간 다른 것을 가질 수 있습니다.

Hanoi tower

int Hanoi( source, mid, destination, height ) {

if ( height == 1 ) { print source '->' destination }
else
   Hanoi ( source, destination, mid, height - 1 ) ; # move all upper tower from source to mid
   print source '->' destination;
   Hanoi ( mid , source, destination, height -1 ) ; # move all the upper tower from mid to destination

}
Hanoi ( "0", "1", "2", 8 );

8 개의 디스크를 소스에서 대상으로 이동하는 솔루션을 인쇄합니다. 보다 http://en.wikipedia.org/wiki/tower_of_hanoi 게임의 규칙을 위해.

"모범 사례"는 구조적 유도를 사용하는 것입니다 (대략적으로는 데이터 구조를 접습니다). 그것이 실패하면, 당신은 일반 (무제한) 재귀를 고려할 수 있습니다.

예를 들어, 목록으로 작업 할 때는 폴드를 사용하는 것이 일반적입니다. 연결 및 부속과 같은 많은 기능은 이러한 방식으로 설명하기 쉽습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top