All Articles

wecode 3주차_3일 TIL_재귀함수(Recursion)에 대해 정리해보기

mathematics-696806_640.png

학창시절.. 수학시간에 프랙탈이라는 구조에 대해서 한번쯤은 들어봤을 것이다. 동일한 모양이 계속해서 반복되는 그러한 구조…!! 사진 속 시에르핀스키 피라밋처럼! 프로그래밍 세계에서도 동일한 함수가 계속 반복되는 재귀(Recursion)라는 개념이 있다.

왜 재귀를 공부해야 할까?

  • 간결하고 직관적인 코드를 제공한다!
  • 설계와 개발, 디버깅 과정모두 재귀적인 사고를 요구한다!

재귀란?

  • 자기 자신을 호출하는 행위
  • 주어진 문제를 자기 반복적인 문제들로 잘게 분해한 후, 이들을 다시 조합해 원래 문제의 정답을 찾는 것을 말한다~

재귀와 콜스택

  • 스택(Stack)이란?

-함수를 호출한 후 원래 자리로 돌아오려면, ‘원래 자리’를 어딘가에 저장해야하는데 그 어딘가를 가리켜 Stack이라고 한다.

  • 호출스택(Call Stack)이란?

-프로그램상 어디에 있는지 기록하는 자료구조를 말한다

cf) MDN 호출스택 정의 : https://developer.mozilla.org/ko/docs/Glossary/Call_stack

-함수를 실행하면 stack위에 push를 하게 됩니다.(쌓이고~)
-return 시 stack의 맨 윗값(가장 최근 데이터)을 pop합니다.(가져오면 그 함수가 cal l stack에서 제거됩니다.)

==> 그래서 return 이란~!

Stack에 저장된 최근 주소값, 나를 실행시킨 것의 바로 다음 step의 주소로 돌아간다는 의미입니다.

  • Stack Overflow

-값이 return 되기 전에 call stack이 쌓이면 호출스택의 최대 수용치를 넘게 되고… stack overflow 발생!!
-종료조건을 달아줘야 stack overflow를 막을 수 있다.

재귀함수 응용

cute-2500929_640.jpg

<1>피보나치 수열

  • 첫 달은 아기 토끼 한 쌍에서 시작합니다.
  • 아기 토끼는 한 달이 지나면 어른토끼가 됩니다.
  • 어른 토끼는 한 달에 한 쌍의 아기토끼를 낳습니다.

==> 0,1,1,2,3,5,8 … 위의 결과가 나오도록 함수를 만들어 보면.. 🙂

    function fibo(n) {
        if (n < 2)
            return n;
        return fibo(n-1) + fibo(n-2);
    }

    fibo(6) // 8

제가 이 코드를 칠 때 우리의 컴퓨터우리의 컴퓨터는…

    call fibonacci(6)
      call fibonacci(5)
        call fibonacci(4)
          call fibonacci(3)
            call fibonacci(2)
              call fibonacci(1)
              return 1
              call fibonacci(0)
              return 0
            return 1
            call fibonacci(1)
            return 1
          return 2
          call fibonacci(2)
            call fibonacci(1)
            return 1
            call fibonacci(0)
            return 0
          return 1
        return 3
        call fibonacci(3)
          call fibonacci(2)
            call fibonacci(1)
            return 1
            call fibonacci(0)
            return 0
          return 1
          call fibonacci(1)
          return 1
        return 2
      return 5
      call fibonacci(4)
        call fibonacci(3)
          call fibonacci(2)
            call fibonacci(1)
            return 1
            call fibonacci(0)
            return 0
          return 1
          call fibonacci(1)
          return 1
        return 2
        call fibonacci(2)
          call fibonacci(1)
          return 1
          call fibonacci(0)
          return 0
        return 1
      return 3
    return 8

위의 식으로 6번째 피보나치 수를 구하는데 무려 함수의 호출이 25번 일어납니다 ㅠㅠ.. 14번째 피보나치 수를 구할땐 호출수는 1019…

console.log(fibo(100)) 을 찍어보면 함수의 호출이 몇 번 일어날까요? (컴퓨터 살려…)

재귀함수의 문제점

  • 함수 호출의 비용
  • Stack의 깊이

그렇다면 해결책은 없을까요…?!

해결책 : 함수 호출하지말고 반복문 쓰기

-반복 단계별 계산 결과를 반복이 끝날 때까지 특정 변수에 저장하는 방식으로 풀어볼 수 있습니다~

    function fibo(n) {
    var cur, pre = 1, prepre = 0;
    if (n < 2)
    return n;
    for ( var i = 2 ; i <= n ; i++ ) {
    cur = pre + prepre;
    prepre = pre;
    pre = cur;
    }
    return cur;
    }

또 다른 해결책으론 꼬리호출이라는 방식이 있는데.. 이건 제가 아직 제대로 이해하지 못해서 다음 기회에…
아직 이 방식을 적용하는 브라우저도 많지 않아서 천천히 알아도 될 것 같고요..?

재귀함수 활용한 알고리즘 문제들

전체코드를 다 보기 전에 타이틀만 보고 꼭 한번씩 생각해보세요~

최소공배수와 최대공약수 구하기

function solution(n, m) {
  function u(n, m) { return m % n ? u(m % n, n) : n; }
  const gcd = u(n, m);
  return [gcd, n * m / gcd];
}

유클리드 호제법이라는 것도 한번 찾아보세요~ 아직도 너무 너무 헷갈리는 이 공식 ㅠㅠ

문자열 반복하기

function repeatString(string, num) {
  if(num <= 0) {
    return ''
  }
  else {
    return string + repeatString(string,num-1)
  }
}

주어진 두 수 사이의 숫자들 구하기

const range = (start = 0, end = 0) => {
  let arr = [];
  start > end && ([start, end] = [end, start]);
  arr.push(start);
  return start === end ? arr : [...arr, ...range(start + 1, end)]
}
console.log(range(2, 5)); // [2, 3, 4, 5]

N번째 짝수 구하기

function getNthEvenNum (n) {
    if (n <= 1) {
        return 0;
    } else {
        return getNthEvenNum(n-1) + 2;
    }
};

getNthEvenNum(3) //4
//0,2,4,6,8,10,12...

특정숫자의 n제곱 구하기

아래의 코드는 2의 n제곱이지만 다른 숫자를 넣으면 그 수의 제곱을 구할수 있겠죠? :)

function getPowerOf2 (n) {
  if(n) <=0) {
    return 1
  }
  else {
    return getPowerOf2(n-1)*2
  }
}

getPowerOf2(4)//16

순차검색법

이건 아직도 헷갈려서 이번에 정리하는 김에 다시 보고 있어요~

function searchArraySequentially (array, i, j, x) {
    if (i <= j) {
        if (array[i] === x) { // 같으면 i return
            return i;
        } else { //같지 않으면 하나씩 늘려서 간격 줄여가기
            return searchArraySequentially(array, i + 1, j, x);
        }
    } else { //끝까지 줄였는데도 안 나오면 i와j사이에 없는거니깐 -1 return
        return -1;
    }
}

var array = ['a', 'b', 'c', 'd', 'e'];
var result1 = searchArraySequentially(array, 0, 4, 'e');
var result2 = searchArraySequentially(array, 0, 3, 'e');

문자열 역순으로 정리하기

거꾸로 하는건 reverse지만.. 언어유희 좀 해봤어요 ㅎ 이 코드를 알고있어서 위코드 1주차 코드카타 문제를 재귀로도 접근해볼수 있었네요~

function rebirth(s) {
  if(s === '') {
    return ''
  }
  else {
    return rebirth(s.substring(1))+s.charAt(1)
  }
}
console.log(rebirth('hello'))
//ello + h
//llo + e + h
//lo + l + e + h
//o + l + l + e+ h

이렇게 재귀에 대해 간단히 알아보았는데요..! 개발자라면 피할 수 없는 부분이라고 생각합니다.. 탈출조건을 생각하고 로직을 짜는게 참 어려운 일이지만..
익숙해지면 잘 할수 있겠죠???!ㅋㅋ

Reference

원래 출처가 몇 군데 더 있었는데.. 예전에 에버노트에서 한번 날리는 바람에…ㅠㅠ
출처 중 두번째 블로그는 읽어보시면 꼭 도움 될겁니다!

Published 14 Aug 2019

안녕하세요. 저의 임시 블로그입니다~ 블로그가 완선되면 핸드메이드 블로그로 이전할 예정입니다!토공 on Twitter