📌 javascript 개념 #9 재귀함수 / 수학기본이론 (1)

재귀함수

재귀함수란 ?

재귀 함수는 함수 안에서 지신의 함수를 호출하는 것이다.
이러한 재귀함수는 특정 조건이 됐을때 자신을 그만 호출하게 할 수 있는 exit code 가 필요하며, 이같은 종료조건이 존재하지 않는다면 무한 반복이 된다.
또, 일반적인 재귀함수로 작성한 코드는 반복문으로도 작성이 가능하다.

---

재귀함수 그림설명

이런 순으로 함수가 실행된다.

---

1. basic recursive function : 기본 재귀함수

function recursive(num) {
  if (num == 0) return 0;
  return num + recursive(num - 1);
}
// 3 + (2 + (1 + 0)) = 0
console.log(recursive(3)); // 6

재귀함수의 일반적인 형식으로, num이 0이면 0이라는 값을 return해주고, 그렇지 않으면 num에 recursive (num - 1) 함수를 더해준 값을 return 한다.
그렇게 되면 num이 3이면 3 + 2 + 1 + 0 순서로 계산이 되며 마지막은 0 이므로 return 0을 하며 계산이 끝나게 된다. 따라서, 답은 6

---

2. factorial function : 팩토리얼 함수

function factorial(x) {
  if (x === 0) return 1;

  return x * factorial(x - 1);
}

const num = 3;

let result = factorial(num); 

// The factorial of 3 is 6
console.log(`The factorial of ${num} is ${result}`);

팩토리얼 함수는 기본적으로 팩토리얼이라는 수학 개념을 먼저 알아야 한다.

팩토리얼이란?

팩토리얼은 차례대로 곱해나가는 수로 예를 들어 5! 일때는 5 ~ 1까지의 수를 전부 곱해서 5 x 4 x 3 x 2 x 1 = 120 이렇게 풀어나가는 것이다.
즉, n부터 1까지의 수를 차례로 곱하는 것이다.

위의 식은 3부터 1까지의 수를 곱하는 factorial이고,
아래는 위에도 예시를 들었던 5!의 예시 코드이다.

let result_2;

function recursive(number) {
  if (number == 1) {
    return number;
  }

  return recursive(number - 1) * number;
}

result_2 = recursive(5); // 5! = 5 * 4 * 3 * 2 * 1
console.log(result_2);
// 120 이 나온다.

우선 recursive라는 함수에서 number가 1이면 number를 return 해준다.
여기서 팩토리얼은 곱해나가는 함수이므로 초기화 값이 1이 되어야만 한다.
number가 1이 아닌 경우에는 recursive 함수를 다시 호출해 number에서 -1한 수를 이전 number에 곱해준 것을 return 해준다.

그렇게 되면 recursive(5) = 5 x 4 x 3 x 2 x 1 이 되며, 120이 나온다.

---

3. AP function : 등차수열

등차수열은 forloop과 재귀함수 두가지의 방법으로 나타낼 수 있는데 우선 재귀함수로 다루는 방법은

let Result;

function recursive(s, t, number) {
  if (number == 1) {
    return s;
  } // break point 
  
  return recursive(s, t, number - 1) +t;
}

// [ 등차수열의 동작원리 ]
// number : 5 , recursive(s, t, 4) => 9 + 2 = 11
// number : 4 , recursive(s, t, 3) => 7 + 2 = 9
// number : 3 , recursive(s, t, 2) => 5 + 2 = 7
// number : 2 , recursive(s, t, 1) => 3 + 2 = 5
// number : 1 ==> 3 => 그냥 s값으로 지정된 3을 내보냄

Result = recursive(3, 2, 5);
console.log(Result);
//  따라서, 11 이 나옴.

등차수열이란?

등차수열은 연속하는 두항의 차이가 일정한 수열이며 즉, 같은 간격(공차)을 두고벌어져 있는 수를 의미한다.
예) 1, 3, 5, 7, 9 ... --> 공차는 2 (공통의 간격 2)

result라는 빈 변수를 우선 선언해주고,
recursive에 s, t, number라는 값을 저장해준다.
만약에 number가 1이라면 s를 return 해준다.
--> 이것이 exit code와 같기 때문에 break point라고 주석을 달아주었다.

만약 number가 1이 아니라면 recursive에 s, t, number - 1을 담은 값에 -t를 해준 값을 return 한다. 나머지는 주석 참고.

---

4. geometric sequence function : 등비수열

등비수열도 등차수열과 비슷하게 foorloop과 재귀함수 모두 구현가능하다.
우선 재귀함수로 구현하는 방법은

let Result_1;

function recursive(s, t, number) {
  if (number == 1) {
    return s;
  }

  return recursive(s, t, number - 1) * t;
}

// [ 등비수열의 동작원리 ]
// number : 5 recursive(s, t, 4) * t => 24 * 2 = 48
// number : 4 recursive(s, t, 3) * t => 12 * 2 = 24
// number : 3 recursive(s, t, 2) * t => 6 * 2 = 12
// number : 2 recursive(s, t, 1) * t => 3 * 2 = 6
// number : 1 ==> 3 => 지정된 s값이 3 이므로

Result_1 = recursive(3, 2, 5);
console.log(Result_1);
// 48 이 나온다.

등차수열이란 ?

등차수열이란 각 항이 첫번째 항과 일정한 비율을 갖는 수열이며 쉽개 말하자면, 같은 비율(공비)을 가지고 떨어져있는 수를 말한다.
예) 1, 2, 4, 8, 16, 32 ... --> 공비는 2

등비수열을 재귀함수로 나타내는 것은 등차수열과 거의 유사하며, 기호만 * 을 써주면 된다. 자세한 건 코드 참조.

---

5. fibonacci numbers : 피보나치 수열

피보나치 수열이란 ?

첫째 및 둘째항은 같으며, 그 다음항은 바로 앞 두 항의 더한 값인 수열이다.
즉 첫째항이 1이라는 가정하에 1, 1, 2, 3, 5, 8, 13 ... 순으로 이어지는 수열이다.
식으로 표현하면 f(n) = f(n-1) + f(n-2)

let Result_2;

function recursive(number) {
  if (number == 1 || number == 0) {
    return number;
  }

  // f(n) = f(n-1) + f(n-2)
  return recursive(number - 1) + recursive(number - 2);
}

// [ 피보나치 수열의 동작원리 ]
// number : 5 -> f(4) + f(3) ==> 3 + 2 = 5
// number : 4 -> f(3) + f(2) ==> 2 + 1 = 3
// number : 3 -> f(2) + f(1) ==> 1 + 1 = 2
// number : 2 -> f(1) + f(0) ==> 1 + 0 = 1
// number : 1 ==> 1



Result_2 = recursive(5);
console.log(Result_2);
// 5 가 나온다.

result_2 라는 빈 변수를 먼저 선언해준다.
만약에 number가 1이거나 0 일때, number를 return 해준다. ( 여기서 || 는 or 연산자 -> '또는' 으로 해석 ) 그 이외의 경우 일때는 recursive(number - 1) 을 한 값과 recursive(number - 2)를 한 값을 더해줘서 return 해준다.

즉 number가 2라면, recursive(1)과 recursive(0) 일때를 더해서 1, 0 을 더한 값인 1이 나와야 한다.