반복 표시

사진 작성자@pkmfaris
막 졸업한 소프트웨어 공학 전공 졸업생으로서 나는 기술 면접을 준비하는 데 많은 시간을 썼다.이 과정의 일부는 데이터 구조와 알고리즘에 대한 지식을 더 많이 배우는 것이다.이 문장에서 나는 왜 유용한지, 그리고 우리가 그것을 어떻게 실현하는지 토론할 것이다.나는 또한 두 가지 흔히 볼 수 있는 귀속 예시를 연구할 것이다. 어떻게 숫자를 1에서 n으로 구하고, 어떻게 귀속 반전 문자열을 사용하는지.

귀속은 무엇입니까?

우리는 만약 함수가 서브루틴으로 자신을 호출한다면 그것은 귀속된다고 말할 수 있다.개인적으로 말하자면, 비록 이것은 이론적으로 의미가 있지만, 귀속되는 작업 원리를 진정으로 이해하려면 시간이 좀 걸릴 수 있다는 것을 알게 되었다.본질적으로 우리가 하는 일은 호출 함수 자체를 통해 일부 문제를 더욱 작은 문제로 분해하는 것이다.일단 우리가 문제를 해결할 수 있고 더 이상 간소화할 필요가 없는 점에 도달하면, 우리는 귀속 호출을 멈추고 답안을 되돌려준다.

교체가 아니라 귀속을 언제 사용합니까?

귀속과 교체는 통상적으로 문제를 유사하게 해결하는 데 쓸 수 있다.그렇다면 우리는 왜 간단한 교체 해결 방안이 아니라 귀속 해결 방안을 선택해야 합니까?결정을 내리려면 다음과 같은 몇 가지를 고려해야 한다.

귀속 함수는 보통 교체 함수보다 짧고 교체 함수는 가능하지만 항상 그렇지는 않습니다!)코드를 더욱 뚜렷하고 읽기 쉽게 하다.

귀속해는 보통 교체해보다 더 복잡한 문제와 구조를 처리할 수 있다.예를 들어 복잡한 트리 구조를 처리하려면 귀속을 사용해야 할 수도 있다.

교체 함수는 보통 귀속 함수보다 빠르기 때문에 만약 프로그램이 교체에 적합하고 속도가 매우 중요하다면 전자를 고려해야 할 수도 있다.

귀속의 단점은 창고 제한이다.만약 이것이 함수와 관련이 있다면, 교체가 더욱 바람직할 수 있습니다.

귀속 원소

반복 함수를 만들 때는 다음 요소를 포함해야 합니다.

기본 사항

는 일반적으로 특정 조건을 충족시킬 때 활성화한다. 예를 들어 입력이 0에 도달했을 때.

(917)case 함수가base에 도착했을 때 호출을 중지합니다.

기본 상황에 도달하는 논리

이것은 함수가 논리를 집행하는 곳이므로 우리는 기본적인 상황에 더욱 가까워질 것이다.

예를 들어 기본 상황의 조건이 입력이 0과 같으면 이 논리는 매번 호출되는 입력에서 1을 줄일 수 있다.

만약 이런 논리가 없다면 우리는 무한순환에 빠질 수 있다.

귀속 호출

귀속 호출은 우리가 함수 자체를 호출하는 곳이다.

사진 작성자@benji3pr

반복 함수 예

예1: 1부터 n까지 귀속구화

이 예에서는 숫자 n을 가져와 1에서 n까지의 모든 숫자의 합을 반환하는 함수를 작성합니다.

const recursiveSumToN = (n) => {

  if (n <= 1) {
    return n;
  } else {
    return n + recursiveSumToN(n - 1);
  }

}

recursiveSumToN(5);

// 15

우리가 Recursive SumTon(5)을 호출할 때, 우리는 1+2+3+4+5의 합을 얻어 15와 같다.
이 기능은 어떻게 작동합니까?위에서 말한 바와 같이 우리는 기본 상황, 기본 상황에 도달하는 논리와 귀속 호출이 필요하다.다음은 이러한 역할을 수행하는 코드 행에 대한 설명입니다.

const recursiveSumToN = (n) => {

  if (n <= 1) {
    // BASE CASE: We want to count the numbers from 1 to n, so we need to stop when n === 1.
    return n; 
  } else {
    // LOGIC TO REACH BASE CASE AND RECURSIVE CALL: If n is > 1, we haven't reached our base case, so we need to call our function again.
    return n + recursiveSumToN(n - 1); 
  }

}

recursiveSumToN(5);

// 15

그래서 n, 즉 입력, 1보다 크면 우리의 함수는 n-1을 사용하여 자신을 호출한다.끊임없이 n을 1로 줄이는 것을 통해 우리는 기본적인 상황을 향해 노력하고 있기 때문에 무한순환으로 끝나지 않는다.
이러한 기능은 다음과 같습니다.

recursiveSumToN(5)
  // this translates to:
  recursiveSumToN(4) + 5
    // =>
    recursiveSumToN(3) + 4
      // =>
      recursiveSumToN(2) + 3
        // =>
        recursiveSumToN(1) + 2
        // 1

이 함수는 두 단계로 나뉘어 일한다.기본 상황에 도달할 때까지 recursiveSumTon을 반복해서 호출합니다.일단 이 기본 상황이 완성되면, 그것은 다른 함수 호출을 해석하기 시작한다.
콘솔을 추가하는 것도 유용하다.코드에 로그인하여 이벤트 발생 순서를 확인합니다.

const recursiveSumToN = (n) => {

    console.log("n: " + n);

    if (n <= 1) {
        console.log("We've hit the base case!");
        return n;
    } else {;
        return n + recursiveSumToN(n - 1);
    }

}

recursiveSumToN(5);

// n: 5
// n: 4
// n: 3
// n: 2
// n: 1
// We've hit the base case!
// 15

그래서 n은 매번 1을 줄이고 우리가 기본적인 상황에 도달할 때까지 함수는 우리의 답안을 되돌려준다.

사진 작성자@robertbye

예 2: 반복 반전 문자열

두 번째 예에서 우리는 문자열, 문자열을 받아들이고 반전시키는 함수를 볼 것이다.이 문제는 여러 가지 방법으로 해결할 수 있는 문제이며, 교체를 포함하지만, 잠재적인 귀속 해결 방안을 살펴볼 것이다.

function recursiveReverseString(string) {

  if (string === "") {
    return ""; 
  }
  else {
    return recursiveReverseString(string.substr(1)) + string.charAt(0);
  }
}

recursiveReverseString("hello");

// olleh

보시다시피 이 함수의 출력은 원시 문자열과 상반된다.이런 상황에서'안녕'은'올리'로 바뀌었다.
아래에서 우리는 기본 상황, 논리와 귀속 호출을 볼 수 있다.

function recursiveReverseString(string) {

  if (string === "") {
    // BASE CASE: Once the string is empty, we have reached our base case.
    return "";
  }
  else {
    // LOGIC TO REACH BASE CASE AND RECURSIVE CALL: One character is removed each time the function is called until we reach our base case.
    return recursiveReverseString(string.substr(1)) + string.charAt(0);
  }
}

recursiveReverseString("hello");
// olleh

우리는 또 일부 컨트롤러를 추가할 수 있다.각 호출에서 문자열의 변경 사항을 보려면 다음과 같이 기록합니다.

function recursiveReverseString(string) {

  if (string === "") {
    console.log("string: " + string);
    console.log("We've hit the base case!");
    return "";
  }
  else {
    console.log("string: " + string);
    return recursiveReverseString(string.substr(1)) + string.charAt(0);
  }
}

recursiveReverseString("hello");

// string: hello
// string: ello
// string: llo
// string: lo
// string: o
// string: 
// We've hit the base case!
// olleh

RecursiveVerseString 함수를 호출할 때마다 빈 문자열이 나올 때까지 한 문자만 줄일 수 있습니다.그리고 함수는 모든 호출을 해석하고 원시 문자열과 반대되는 문자열을 출력합니다.

연습하다

귀환을 실현할 수 있는 것은 특히 기술 면접에서 매우 유용하다.HackerRank,Codewars와 LeetCode는 여러 가지 귀속 연습을 바탕으로 당신에게 더 많은 내용, 발전 기능과 연습을 배울 수 있습니다.

출처

"When To Use Recursion/When To Use Iteration", CSIE, 2020년 11월 6일 방문

"Principle of Recursion", 리트코드, 2020년 11월 6일 방문

"What is the function of recursion? Why do we need recursion in programming?", Quora, 2020년 11월 6일 방문

", 크리스티나 맥마흔(Christina McMahon)은 2020년 11월 6일 DEV 홈페이지

에 게재됐다.

"Recursion and Stack", 크리스티나 맥마홍이 개발에 관한 글을 2020년 11월 6일 발표