>

누군가이 재귀 함수를 살펴보고, 코드에 대한 조언을 제공하거나, 재귀 적으로 사고하려는 비판을 비난 할 수 있습니까?

문제 :

We’ve seen that % (the remainder operator) can be used to test whether a number is even or odd by using % 2 to see whether it’s divisible by two. Here’s another way to define whether a positive whole number is even or odd:

  • Zero is even.
  • One is odd.
  • For any other number\$N\$, its evenness is the same as\$N - 2\$.

Define a recursive function isEven corresponding to this description. The function should accept a single parameter (a positive, whole number) and return a Boolean. -eloquentJavascript, chapter 3

내 시도 :

function isEven(x) {
  if (x < 0 ) {
        return false
  }
   else if (x % 2 == 0) {
        return true
  } else {
        return isEven(x-2)
  }
}

공식 솔루션 :


function isEven(n) {
  if (n == 0)
    return true;
  else if (n == 1)
    return false;
  else if (n < 0)
    return isEven(-n);
  else
    return isEven(n - 2);
}

동일한 기능을 작성하는 많은 방법이 있다는 것을 알고 있지만 다음 코드가 철저히 조사되는지 알고 싶습니다. 코드를 확인한 공식 솔루션은 분명히 다르지만 올바른 솔루션을 얻습니다.

console.log(isEven(50));
// → true
console.log(isEven(75));
// → false
console.log(isEven(-1));
// → false

어떤 이벤트가 발생합니까?

else if (n < 0)
    return isEven(-n);

그것을 처리

else
    return isEven(n - 2);

아니요?

재귀 적으로 생각하는 방법을 배우기 위해Douglas Crockford의 조언에 따라'작은 Schemer'를 읽기 시작했지만 예제는 Scheme 에 있습니다.  나에게 (((n) * atom))처럼 보입니다 ... 구문을 읽을 때까지는별로 유용하지 않습니다.


  • 답변 # 1

    솔루션은 거의 비슷합니다.

    나머지 연산자 % 를 사용하고 있습니다 , 요점은 그것을 수행하지 않는 것입니다 (운동의 목적으로-다른 경우에는 반드시 % 를 사용하십시오) ).

    공식 솔루션은 숫자 0과 1에 대해 참/거짓에 답하는 방법 만 알고 있습니다. 다른 입력의 경우 재귀를 사용하여 입력을 0 또는 1로 줄입니다. 또한 순서대로 음수를 뒤집습니다. 그것들을 0 또는 1 *로 가져옵니다.

    귀하의 솔루션은 재귀없이 긍정적 인 짝수에 대해 즉시 응답합니다. 따라서전체 운동을 회피하고 있습니다. true 에 대답 할 수 있다면 코드가 거의 이해되지 않습니다.  즉시, 그것은 당신이 false 에 대답 할 수 있습니다 따라  즉시도. 그것들이 유일하게 가능한 반환 값이므로 true 가 아닌 경우  논리적으로필수false . 첫 번째 경우에 대해 되풀이하지 않기 때문에 왜 두 번째 경우에 대해 되풀이해야합니까?

    또한 공식 코드와 달리 코드에서 모든 음수를 홀수로 처리합니다. 그리고 일반적으로 수학.

    이 모든 것을 다른 방식으로 표현하려면 : 공식 솔루션은이 지식으로 문제에 접근합니다 :

    0도 짝수입니다

    1이 홀수입니다

    우리는 다른 숫자의 패리티에 대해 아무것도 모른다

    그러나 2를 반복적으로 빼고 숫자가 음수이면 부호를 뒤집어 숫자를 0 또는 1로 줄일 수 있습니다.

    따라서 0 또는 1이 아닌 숫자에 대해서는 되풀이해야합니다.

    당신의 접근 방식은 다음과 같습니다.

    2로 나눌 수있는 숫자는 짝수입니다 (속임수)

    음수가 홀수 (잘못된)입니다.

    2를 계속 빼면 다른 숫자는 음수가됩니다

    마지막으로 2로 나눌 수없는 숫자는 자동으로 홀수입니다. 그러나 코드는 이러한 도약을 만들지 않고 대신 (무의미한) 재귀를 사용합니다.

    어떤 해결책도 숫자 (!)의 패리티를 결정하기위한좋은해결책은 아니지만, 문제 설명의 맥락을 모르고 요점은 재귀를 사용하는 것입니다. 특정 숫자에 대해 범주 적으로 대답 할 수있는 것으로 드릴 다운합니다. 즉 0은 짝수이고 1은 홀수입니다. 귀하의 솔루션은세트, 즉 양의 짝수 및 음수에 대해 답변합니다.

    *)이 모든 것에서 우리는 입력이 항상정수이고 다른 것이 아니라고 가정합니다. 예, 입력 유효성 검사를 수행 할 수는 있지만 연습 범위 및이 검토 범위를 벗어납니다

  • 답변 # 2

    이 두 가지 모두 끔찍하게 비효율적 인 것처럼 보이지만 강제로 사용하면 얻을 수 있습니다. 이 문제를 해결하기 위해 재귀를 사용합니다.

    어쨌든 입력의 유효성을 검사하지 않습니다. 처음에 정수 값을 전달받지 못하면 어떻게 되나요?

    솔루션이 음의 정수를 올바르게 처리하지 않습니다. 왜 이것이 항상 거짓을 반환합니까?

    귀하의 솔루션은 불필요하게 재귀를 사용한다는 점에서 정말 이상합니다. 모듈러스를 사용하려는 경우 전혀 재귀 할 필요가 없습니다. 이 작업 직후에 참 또는 거짓을 알고 있으며 숫자에서 2를 줄이면 되풀이해도 결과가 바뀌지 않습니다. 마지막으로<0의 가치에 도달 할 때까지 시간이 더 걸립니다.

    제안 된 솔루션과 비슷한 것이 있지만 일부 입력 유효성 검사가 추가되었습니다.

    function isEven(n) {
      // make sure we have a number
      if(isNAN(n)) {
        console.log('Non-integer passed to isEven()');
        return false;
      }
      // parse it as int to weed out floats
      if(n !== parseInt(n)) {
        console.log('Non-integer passed to isEven()');
        return false;
      }
      if (n === 0)
        return true;
      else if (n === 1)
        return false;
      else if (n < 0)
        return isEven(-n);
      else
        return isEven(n - 2);
    }
    
    

관련 자료

  • 이전 java - 목표 합계를 가진 두 숫자 찾기
  • 다음 c# - leetcode - 왼쪽 하단 트리 값 찾기