두 개의 숫자를 연속적인 뺄셈을 사용하여 구하는 재귀 함수

Question

시도했지만 실패했습니다. 올바른 방향으로 밀어 넣을 수 있을까요?

Answer 1

먼저 대개 이것은 재귀를 위해 대단히 나쁜 사용법임을 강조해야합니다. 최상의 재귀 적 솔루션은 이터 레이션마다 나머지 검색 공간의 절반을 제거하는 바이너리 검색과 같이 솔루션의 "검색 공간"을 다소 빨리 줄이는 경향이 있습니다.

감산이 피검자에 비해 상대적으로 작은 경우 (minuend - subtrahend은 차이를 나타냄) 많은 재귀 호출이 발생하고 스택 공간을 상당히 소모 할 수 있습니다.

---

은 아마 숙제이기 때문에 아래의 솔루션은 단지 의사 코드에 그런 말로 미루어 보아 :

그것은 당신이 때까지 반복 a에서 b을 뺀 및 수준을 아래로 이동하여 작동

def divu (a, b): 
    if a < b return 0 
    return divu (a - b, b) + 1 

부정적인 영향을받지 않고 더 이상 b을 a에서 뺄 수 없습니다. 그런 다음 재귀 트리를 반환하고 내려간 각 레벨에 대해 1을 더합니다.

이는 단지 원판 대를 고정했지만, a의 음이 아닌 값 b의 양수 값 (부호위한 따라서 divu 이름) 작동 및 제로 나눗셈 것이다 단지 약간의 추가 작업이다. 취급 표지판 및 오류

몇 가지 힌트 : b는 오류, 예외, 또는 다른 메커니즘 제로 종료에 동일한 경우는

• 똑바로 감지합니다.
• -a/-b을 a/b으로 처리하십시오.
• -a/b을 -(a/b)으로 처리하십시오.
• a/-b을 -(a/b)으로 처리하십시오.
• 그렇지 않으면 a/b을 해결하십시오.

그것은 하나의 재귀 호출에서 그 특별한 경우를 처리하는 것이 가능하지만, 재귀의 각 수준에서 불필요한 검사를 추가합니다. 질문을 당신이 실패하는 방법

def div (a, b): 
    if b == 0 
     exit with error 
    if a < 0 and b < 0: 
     return divu (-a, -b) 
    if a < 0: 
     return -divu (-a, b) 
    if b < 0: 
     return -divu (a, -b) 
    return divu (a, b)