Recursion

  • 재귀함수
  • 자기 자신을 호출하는 함수
  • 무한 루프에 빠지지 않도록 조건을 잘 세워야한다.
    • Base case: 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다.
    • Recursive case: recursion을 반복하다보면 결국 base case로 수렴해야 한다.

기본적인 수학함수에서의 Recursion 예

Factorial: n!

  • Recursion 관점에서의 접근
    • 0! = 1 : Base case
    • n! = n * (n-1)! if n>0 : Recursion case
function factorial(n) {
  if (n == 0) return 1;
  else return n * factorial(n - 1);
}

power (x^n)

  • Recursion 관점에서의 접근
    • x^0 = 1 : Base case
    • x^n = x*x^n-1 if n>0 : Recursion case
function power(x, n) {
  if (n == 0) return 1;
  else return x * power(x, n - 1);
}

Fibonacci Number

  • Recursion 관점에서의 접근
    • f0 = 0 : Base case
    • f1 = 1 : Base case
    • fn = fn-1 + fn-2 if n>1 : Recursion case
function fibonacci(n) {
  if (n < 2) return n;
  else return fibonacci(n - 1) + fibonacci(n - 2);
}

최대공약수 gcd

  • m>n인 두 양의 정수 m과 n에 대해서 m이 n의 배수이면 gcd(m, n)=n이고,
  • 그렇지 않으면 gcd(m, n)= gcd(n, m%n)이다.
  • Recursion 관점에서의 접근
    • if n == 0 return n : Base case
    • gcd(m, n) = gcd(n, m%n) : Recursion case
function gcd(m, n) {
  if (m < n) {
    var temp = m;
    m = n;
    n = temp;
  }
  if (n == 0) return m;
  else return gcd(n, m % n);
}

다른 예(일반적으로 반복문으로 행하는 동작들)

  • 일반적으로 반복문으로 하는 모든 동작은 Recursion으로 나타낼 수 있다.
  • 즉, 모든 Recursion은 반복문으로 변경이 가능하다.
  • Recursion은 복잡한 알고리즘을 단순하고 알기쉽게 표현하는 것을 가능하게 한다.
  • 하지만 함수 호출에 따른 오버헤드가 있다.(매개변수 전달, 액티베이션 프레임 생성 등)

이진수로 변환하여 출력

  • Recursion 관점에서의 접근
    • if n < 2 return n : Base case
    • f(n / 2) : Recursion case
    • return n%2 : Recursion case
function printInBinary(n) {
  if (n < 2) {
    console.log(Math.floor(n));
  } else {
    printInBinary(n / 2);
    console.log(Math.floor(n % 2));
  }
}

data[0]에서 data[n-1]까지의 합

  • Recursion 관점에서의 접근
    • if n < 0 return 0 : Base case
    • return f(n-1) + data[n-1] : Recursion case
function sum(n, data) {
  if (n <= 0) {
    return 0;
  } else {
    return sum(n - 1, data) + data[n - 1];
  }
}

Designing Recursion(순환적 알고리즘 설계)

  • 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 한다.
  • 모든 case는 결국 base case로 수렴해야 한다.
  • 암시적 매개변수를 명시적 매개변수로 바꿔야 한다.
    • 맨 처음 호출될 때의 상황 뿐아니라 Recursive하게 호출될 때의 상황을 고려해야한다.
    • 즉, 함수를 일반화시켜야 한다.
    • 명시적 매겨변수 사용

순차 탐색

  • 반복문을 사용한 순차탐색을 Recursion 함수로 변경한다.
  • 시작 위치를 명시적으로 입력해준다.
function LinearSearch(data, n, target) {
  for (var i = 0; i < n; i++) {
    if (data[i] == target) return i;
  }
  return -1;
}

이 함수의 미션은 data[begin]에서 data[end] 사이에서 target을 검색한다. 즉, 검색구간의 시작점을 명시적으로 지정한다.

function LinearSearch(data, target, begin, end) {
  if (begin > end) {
    return -1;
  } else if (target == data[begin]) {
    return begin;
  } else {
    return LinearSearch(data, target, begin + 1, end);
  }
}

최대값 찾기

  • 이 함수의 미션은 data[begin]에서 date[end] 사이에서 최대값을 찾아 반환한다.
  • begin<=end라고 가정한다.
function findMax(data, begin, end) {
  if (begin == end) {
    return data[begin];
  } else {
    return Math.max(data[begin], findMax(data, begin + 1, end));
  }
}
  • items[begin]에서 items[end] 사이에서 target을 검색한다.
function binarySearch(arr, target, begin, end) {
  if (!begin) begin = 0;
  if (!end) end = arr.length;

  if (begin > end) {
    return -1;
  } else {
    var mid = (begin + end) / 2;
    if (target == arr[mid]) {
      return mid;
    } else if (target < arr[mid]) {
      return binarySearch(arr, target, begin, mid - 1);
    } else {
      return binarySearch(arr, target, mid + 1, end);
    }
  }
}

참고