재귀 함수 모범 사례; 그들은 무엇인가?

Question

재귀 함수를 설계 다른 언어에 독립적 인 방법은 일반적인 이외의 무엇 :

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

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

감사합니다. :)

Answer 1

지연 프로그래밍 언어에서는 끝점을 정의하지 않는 재귀를 사용할 수 있습니다. 결과는 무한한 데이터 구조 일 수 있지만 모든 데이터 구조를 사용하지 않는 한 괜찮습니다. 예를 들어, 하스켈 전체 피보나치 시리즈를 정의하는 일반적인 방법이있다 :

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

이 다음 영어로 변환 : 피보나치 시리즈는 엘리먼트 -이 시리즈이어서 1이어서 1 첫 번째 요소가없는 피보나치 시리즈와 피보나치 시리즈의 현명한 합.

이것은 재귀 함수 호출보다는 재귀 적 정의처럼 들리지만, 하스켈에서는 커다란 구별이 없습니다. 위의 것은 인자가없는 '무효 함수'입니다.

일반적으로 이것을 사용하려면 fibS의 첫 번째 N 요소 만 사용하면됩니다. 프로그램을 영원히 계속 사용하는 것이 좋다면 모든 것을 실제로 사용할 수 있습니다 :-)

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

편집 : 이러한 원칙은 '게으름'의 일부 요소가있는 경우 다른 언어에도 확실히 적용될 수 있습니다. 파이썬을 파이썬으로 포팅 한 위의 구현은 다음과 같습니다.

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())) 

하스켈 버전만큼 효율적이지는 않습니다. 일부 해킹과 일종의 전역 객체를 사용하면 더 효율적으로 만들 수 있습니다. 그러나 명확한 종료 조건이 없음을 주목하십시오.

Answer 2

자, 당신은 일부 재귀를 중지하는 방법을 알고 있어야합니다. 그게 당신의 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); 

Answer 3

꽤 많이 있습니다.

재귀 함수 디자인은 "값을 반환 할 수 있습니까? 아니면 추가 처리를해야합니까?"와 같이 간단합니다. "처리가 그걸로 값을 돌려주었습니다. 내가 그것을 전달하기 전에 내가 무엇을해야합니까?"

꼬리 재귀는 컴파일러/인터프리터가 성능을 향상시키는 데 사용할 수있는 최적화 방법입니다. 본질적으로 재귀 함수가 엄격한 형식을 따르는 경우 (재귀 호출 이후 아무 일도 일어나지 않습니다. 일반적으로 재귀 호출은 항상 return과 쌍을 이룬다는 것을 의미합니다) 재귀 함수는 최적화되고 for 루프로 다시 작성 될 수 있습니다.

Answer 4

귀하의 궁금한 점은 무엇입니까? 그냥 시도하는 몇 가지 답변 ;-)

재귀의 많은 종류가 있습니다

• "표준"재귀

  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() 
  

• Fixed-Point 재귀

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

그리고 재귀의 응용 프로그램 목록이 매우 풍부하다. 함수형 프로그래밍에서 모든 반복 코드 (for-loops 등)는 재귀를 통해 표현됩니다!

또 다른 좋은 예 :

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

재귀 당신이 일반적으로 함수를 자기 전화 할게, 그래서 당신의 종료 조건이 어떤 점에서 만족 있는지 확인하는 것입니다의 주요 "모범 사례" " 더 작은 "데이터를 사용합니다 (트리의 한 부분 만). 다른 모든 것들은 끝없는 재귀를 초래할 수 있습니다.

Answer 5

재귀를 중지하려면 테스트를 거쳐야합니다.

하지만 당신은 하노이 타워 알고리즘 (2 재귀 호출)처럼 조금 다를 일을 할 수 있습니다 :

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을 참조하십시오.

Answer 6

Google은 recursion에 대한 많은 정보를 가지고 있습니다. :)

Answer 7

은 변화의 많은 예를 들어, 다음과 같습니다

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

그들이 모두가 공통적으로 가지고있는 것은 그들이 작은 작업으로 작업을으로 나눔이다

다음 자체를 사용 작은 작업을 해결할 수있을만큼 작아서 사소한 작업으로 해결할 수 있습니다.

Answer 8

"모범 사례"는 구조적 유도 (대략적으로 데이터 구조에 대한 폴드)를 사용하려고하는 것입니다. 이것이 실패하면 일반 (제한되지 않은) 재귀를 고려할 수 있습니다.

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