알고리즘 점화식(등차수열, 팩토리얼, 피보나치 수열)

알고리즘, 점화식(등차수열, 피보나치 수열)

점화식(재귀식)

점화식, 재귀식이란 수열에서 이웃하는 두 개의 항 사이에 성립하는 관계를 나타낸 관계식을 말한다.

대표적인 점화식에는 등차 수열, 등비수열, 팩토리얼, 피보나치 수열이 있다.

• 등차 수열 : F(n) = F(n - 1) + a
• 등비수열 : F(n) = F(n - 1) * a
• 팩토리얼 : F(n) = F(n -1 ) * n
• 피보나치수열 : F(n) = F(n - 1) + F(n - 2)

등차수열

for 반복문을 활용한 등차수열 알고리즘이다.

function forloop(첫항, 공차, N번째){
  let N번째항 = 0;
  
  for(let i =1; i <=N번째; i++){
    if(i === 1){
      N번째항 += 첫항
    } else {
      N번째항 += 공차
    }

  }
	return N번째항
}

forloop(3,2,5) // 11

재귀식으로 간단하게 표현할 수 있는데 다음과 같다.

function recursive(첫째항, 공차, N번째){
  // 멈출 조건
  if(N번째 === 1){
    return s;
  }
  // 반복할 코드
  return recursive(첫째항, 공차, N번째 - 1) + t
  
  // number : 5, recursive(첫째항, 공차, 4) + 2 : 9 + 2
  // number : 4, recursive(첫째항, 공차, 3) + 2 : 7 + 2
  // number : 3, recursive(첫째항, 공차, 2) + 2 : 5 + 2
  // number : 2, recursive(첫째항, 공차, 1) + 2 : 3 + 2
  // number : 1 => 3
}

recursive(3,2,5) // 11

아래는 수학 공식을 가지고 구현한 식이다.

function forloop2(첫항, 공차, N번째){
  let N번째항 = 첫항 + ((N번째 - 1) * 공차)
  return N번째항
}

 

팩토리얼

팩토리얼은 1부터 n까지 곱한 수를 의미한다. 재귀 함수로는 아래와 같이 풀을 수 있다.

let result;

function recursive(number){
  if(number === 1){
    return number
  }
  // 5 4 3 2 1
  return recursive(number - 1) * number
}

recursive(5) // 120

익숙한 for문으로는 아래처럼 풀이될 수 있다.

function solution(n){
  let result = 1
  for(let i=1;i<=n;i++){
    result *= i
  }
  return result
}

solution(5) // 120

 

피보나치 수열

피보나치수열은 첫째 항과 둘째 항의 합이 셋째 항이 된다.

f(n) = f(n-1) + f(n-2)를 의미하며 재귀 함수로 풀 수 있다.

let result;

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)
  // recursive(4) + recursive(3)
  // recursive(3) + recursive(2) + recursive(2) + recursive(1)
  // recursive(2) + recursive(1) + + recursive(1) + recursive(0) + recursive(1) + recursive(0) + recursive(1)
  //recursive(1) + recursive(0) + recursive(1) + recursive(1) + recursive(0) + recursive(1) + recursive(0) + recursive(1)
}


recursive(5)

 

학습 회고

등차수열, 팩토리얼, 피보나치수열들이 수학식으로는 쉽게 풀었다가 알고리즘으로 풀려니 막혔던 게 많았다. 매번 반복문으로 풀이를 하다가 막혔던 부분들이 많았는데 재귀함수로 더 쉽게 풀 수 있다는 걸 느꼈다. 아직까지 재귀함수가 어색하기 때문에 계속 쓰면서 익숙해져야겠다. 재귀함수에서 가장 중요한 것은 멈추는 식이 있어야 한다는 것! 잊지 말자.

 

이전 글들

2022.08.11 - [분류 전체보기] - 알고리즘, 시간 복잡도와 경우의 수 기본 개념

알고리즘, 시간 복잡도와 경우의 수 기본 개념

2022.08.11 - [분류 전체보기] - 리액트에 대한 이해, 자바스크립트와 비교

리액트에 대한 이해, 자바스크립트와 비교

2022.08.10 - [분류 전체보기] - 스코프와 호이스팅 개념과 예시코드

스코프와 호이스팅 개념과 예시코드