This week I learned - 재귀편

재귀란?
스스로 함수를 호출하는것

function foo(){
 foo();
}

위의 경우 재귀함수 호출의 탈출 조건을 넣지 않으면 무한 호출되게 되기때문에,재귀호출을 사용시엔 반드시 탈출 조건을 넣도록 하자.

** 피보나치 수열 재귀함수 : fib(n) = fib(n-1)+fib(n-2)

function fib(n){
 if(n===0){
	return 0;
 }
 if(n ===1){
  return 1;
}
 return fib(n-1) + fib(n-2);
}

재귀의 장점

알고리즘이 재귀로 표현하기 자연스러울 경우
프로그램의 가독성이 좋아진다.

재귀 단점

값 리턴전까지 호출마다 콜스택 새로 생성하므로 메모리를 많이 잡아 먹는문제가 있다.

재귀를 이용한 알고리즘 문제풀이 예시 - 제곱근 계산

---

Math.sqrt()를 이용하면 손쉽게 제곱근값을 구할수 있다. 이 알고리즘은 어떻게 구현해야 할까? while문과 재귀를 이용한 2가지 방법 비교를 통해 살펴보도록 하자.
우리가 사용할 알고리즘은, 바빌로니아 법을 이용한 계산법으로,(위키:https://ko.wikipedia.org/wiki/%EB%B0%94%EB%B9%8C%EB%A1%9C%EB%8B%88%EC%95%84_%EB%B2%95)
바빌로니아 법(The Babylonian Method)은 임의의 수의 제곱근에 빠르게 수렴하는 수열을 만들어 근삿값을 구하는 방법으로써, 아래와 같은 식을 통해 근사값을 구할 수 있다.

x = (x + (a / x)) / 2      

a는 제곱근을 구하고자 입력되는 값이고 x 는 0~ a 사이에 존재하는 임의의 값.

-> 이 수식을 원하는 근사치가 나올때까지 반복 루프 돌려서 제곱근 값을 구할수 있다.

> While루프를 이용한 방법

function computeSquareRoot(num) {

    let start = num;
    let err = 0.0000001;

    while( (start-num/start)> err){
        start= (start+ num/start)/2;
        console.log(start);
    }
    return Number(start.toFixed(4));
}

While 루프를 이용해 제곱근 값을 구한것을 재귀를 이용해 다시 풀어보면 아래와 같다.

> 재귀를 이용한 방법

function computeSquareRoot(num, guess) {
   
    if ( !guess ) {
        guess = num / 2; // 초기 추측값
    }
  
    let divide = num / guess;// 숫자를 추측값으로 나눔
    let new_guess = ( divide + guess ) / 2;

    if ( guess === new_guess) {
      // 만약 이전 추측값이 새 추측값과 같다면
      // 더 이상 정말한 근사값을 구할수 없으므로 최종 근사값을 리턴 
        return guess;
    }
    //재귀를 통해 반복 호출
    return computeSquareRoot(num, new_guess);
}