TIL 2020-11-18(復帰)

Week 4-2:再帰的思考
TIL List
理解

練習

再帰思考

1)鬼?
国語辞典によると、「再帰位」は「元の位置に戻るか元の位置に戻るか」である.上に書いてあります.
したがって,再帰関数とは,独自の形式を呼び出す(返す)関数である.繰り返しの形式から見ると,繰り返し文(For,Whlie)といえる.
特定の配列の要素の和を求めるコードが記述されていると仮定します.
繰り返し文を十分に理解すれば、次のコードを書くことは間違いありません.

let arr = [1,2,3,4,5];
function getArrSum (arr) {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    sum = sum + arr[i]
  }
  return sum; // getArrSum(arr) === 15 -> true
}

以上のように,arrの要素の和は文を繰り返すことで容易に求めることができる.
今回は上の問題を再帰的な思考と見なした.
2)再帰的思考の練習

arrの要素[1,2,3,4,5]の合計が必要であり、合計は1+2+3+4+5であるべきである.

1回の計算

は複雑で、私たちはそれに迫っています.まず2+3+4+5の和を求めます.

これも複雑で、3+4+5の和を求めます.

もう少し簡潔に4+5の和を求めます.上記の問題を再帰的に考えることでコード化すると、以下のようになります.

arrSum([1,2,3,4,5]) = 1 + arrSum([2,3,4,5]) = 1 + 14 = 15
arrSum([2,3,4,5]) = 2 + arrSum([3,4,5]) = 2 + 12 = 14
arrSum([3,4,5]) = 3 + arrSum([4,5]) = 3 + 9 = 12
arrSum([4,5]) = 4 + arrSum([5]) = 4 + 5 = 9
arrSum([5]) = 5 + arrSum([]) = 5 + 0 = 5
arrSum([]) = 0;

問題を解決する過程を見分けることができる.
同様に、再帰的思考は、ある問題を解決する際に、構造が同じであるがより小さい問題を解決することによってその問題を解決する方法を再帰的思考と呼ぶ.
実際、すべての再帰関数はwhile/forループで表すことができますが、再帰が有効になっている場合、再帰を使用するコードは多くの場合より簡潔で、場合によっては理解しやすい場合があります.
しかし、上記のコードには問題があります.すなわち、明確な脱出条件はない.
そのため、このコードは自分がいつまでこのことを繰り返すのか分からないまま、果てしない繰り返しを経て、最終的にMAXIMUM CALL STACKという惨めな結果になる.
ここから分かるように,再帰関数も繰返し文のように脱出条件を明確にしなければならない.
したがって、脱出条件は次のように設定できます.

1. 만약, arr의 길이가 0일 경우, 즉 빈 배열일 경우 0 을 리턴한다.

2. 1번을 이용해 arr의 요소를 모두 돌아서 arr의 요소가 더 이상 존재하지 않을 때까지 반복한다.

3. 그 외의 경우는 첫 요소 arr[0] 에 나머지 배열을 모두 더한다.

コードで記述しようとすると、次のようになります.

let arr = [1,2,3,4,5];

function arrSum(arr) {
  if (arr.length === 0) { // 탈출 조건
    return 0;
  } 
  const head = arr[0]; 
  const tail = arr.slice(1);  
  return head + arrSum(tail)
}

arrSum(arr) // 15

上を見ても、このコードがどのように動作しているのか理解できないかもしれません.次は上のコードの作業手順です.

head = [1] tail = [2,3,4,5]  // 처음 함수 실행 시 head, tail 의 값
return [1] + arrSum([2,3,4,5])

head = [2] tail = [3,4,5]  // return 을 통해 다시 실행된 함수의 head, tail 값
return [2] + arrSum([3,4,5])

head = [3] tail = [4,5]  // return 을 통해 다시 실행된 함수의 head, tail 값
return [3] + arrSum([4,5])

head = [4] tail = [5]  // return 을 통해 다시 실행된 함수의 head, tail 값
return [4] + arrSum([5])

head = [5] tail = []  // return 을 통해 다시 실행된 함수의 head, tail 값
return [5] + arrSum([0])

// tail이 빈 배열, 즉 입력받은 arr이 빈 배열이므로 조건문에 따라 0을 리턴한다.
// arrSum 에 0의 값을 받았으므로 역순으로 다시 올라가면서 합을 구한다.

5 + 0  = 5       //  return [5] + arrSum([0])
5 + 4 = 9        //  return [4] + arrSum([5])
9 + 3 = 12       //  return [3] + arrSum([4,5])
12 + 2 = 14      //  return [2] + arrSum([3,4,5])
14 + 1 = 15      //  return [1] + arrSum([2,3,4,5])

変数headを基準として、tailの各要素が加算されていることがわかる.