재귀함수

백승용·2020년 10월 14일
1

재귀함수란

함수가 자기 자신을 호출하는 것

예시) 팩토리얼
5!
=5x4!
=5x4x3!
=5x4x3x2!
=5x4x3x2x1

function fac(n){
    if(n === 1) return 1;
    return n * fac(n-1);
}

fac(4) // 결과 24

재귀적으로 사고하는 법

1. 문제를 잘게 쪼개고 경우의 수를 생각해본다.

  • 어떤 기준(크기와 순서)으로 잘게 나눌 것인지 정한다. 그리고 잘게 나눈 경우의 수도 생각해본다.
  • 처음 입력 받은 배열은 탈출 조건에 해당하면 안된다.
  • 재귀호출 시 입력 받는 데이터 타입을 같게 해준다. 예를 들어, arrSum함수의 입력 받는 인자는 배열이고 함수는 그 배열을 처리한다.
  • 재귀호출한 함수와 재귀함수는 다른 공간이라고 생각하면 된다. 그래서 재귀함수의 변수와 재귀호출한 함수의 변수는 다른 변수이고 그 변수를 return 값 또한 다르다.

2. 탈출 조건을 정한다.

  • 더이상 나눌 수 없을 경우 어떻게 return할 지 정하는 것으로 재귀함수를 탈출할 수 있다. 탈출조건을 정하지 않거나 잘 못 정할경우 무한 loop가 걸릴 수 있다.

배열의 합 구하기

let arr = [1,2,3,4,5]
console.log(arrSum(arr)); // 결과 : 15

  • 배열의 요소의 합을 구하는 함수는 for문으로 작성가능하지만 for문을 사용하지 않고 재귀 함수를 통해 작성 가능하다.

  • 먼저, 배열의 첫번째 요소와 그 뒤의 요소들로 나눌 수 있다.(크기를 나눈다.)
    1 + [2,3,4,5]

  • 다시 뒤의 배열을 첫번째 요소와 나머지 배열로 나눌 수 있다.
    2 + [3,4,5]
    3 + [4,5]
    4 + [5]
    5 + []

  • 위의 예시에서 탈출 조건은 마지막의 빈 배열일때 값을 0으로 해주거나 아니면 배열의 길이가 1일때 요소를 return한다.

if(arr.length === 0){
  return 0;
}

if(arr.length === 1){
  return arr[0];
  • 탈출 조건이 아닐 경우 return 값으로 재귀호출한다. 
return arr[0] + arrSum(arr.slice(1)) // 크기를 나눈 코드

재귀의 장점

  • 직관적인 코드와 가독성을 높여준다.

재귀의 단점

  • 재귀 호출을 두겹 이상으로 사용하면 함수 호출 횟수가 엄청나게 증가하여 연산이 끝나지 않는다.
  • 재귀의 깊이가 깊어질수록 메모리를 많이 사용한다.

해결

  • 재귀 호출 대신 반복이나 Tail Recursion 방식으로 구현하면 문제 상황을 피해갈 수 있다.
  • JavaScript처럼 실행 환경에서 Tail Call Optimization을 지원해주지 않으면 사실 상 유일한 해결책은 반복문 뿐이다.

재귀의 깊이

  • Math.pow(x,n)메서드를 사용하지 않고 제곱하는 함수를 코딩해보자
  • 2^4을 예로 들어보자
    2^4 = 22^3
    2^3 = 2    2^2
    2^2 = 2*2^1
    2^1 = 2
  • 탈출 조건은 n이 1일때, x를 리턴해준다.
  • 이때, 재귀의 깊이는 n개이다.

코딩으로 옮겨보자

function pow(x,n){
  if(n === 1) {
    return x
  }
  return x * pow(x,n-1);
}

재귀함수 사용 시 메모리의 한계

  • 중첩 함수를 호출할 때 실행(execution) context stack에 현재 실행 context를 저장한다.
  • 실행 context stack에 들어가는 실행 context 수만큼 메모리 사용량이 늘어난다. 즉, n값이 커질 수록 메모리 사용량이 증가한다.
  • 재귀의 깊이는 실행 context stack에 들어가는 실행 context 수의 최대값과 같다.
  • 실행 context는 메모리를 차지하므로 재귀를 사용할 때는 메모리 요구사항에 유의해야한다.

함수호출 횟수가 많아 끝나지 않는 연산

  • fibonacci(100) : 피보나치 100자리인 값은 354,224,848,179,261,915,075이고 함수 호출은 이보다 2배 이상의 호출을 한다.컴퓨터가 멈추지 않는게 신기하다 (O.O)
  • 함수호출의 횟수는 (앞의 두수를 구한 값 +1)이다.
function fibonacci(num){
  if(num <=1){
    return num;
  }
  return fibonacci(num - 1) + fibonacci(num - 2);

반복문으로 해결한다.

function fibonacciLoop(num){
  let first = 0, second = 1
  let current = 0;
  
  if(num <= 1){
    return num
  }
  
  for(let i = 2; i <= num; i++){
    current = first+second
    first = second
    second = current
  }
  return current
}

Tail Call이란

  • Tail Call은 함수를 호출해서 값을 반환 받은 후 아무 일도 하지 않고 바로 반환하게 하기 위해 논리적으로 가장 마지막(꼬리) 위치에서 함수를 호출하는 방식을 말한다.
  • Tail Call 방식을 적용하려면 두 겹인 재귀 호출을 한 겹으로 줄여야만 한다.
function a() {
    var v = 0;
    return b(v--);
}
function b(n) {
    return n + 1;
}
a(); //결과 : 1, 우리가 생각하는 Tail Call로 코딩해보았지만 값은 0이 아닌 1이다. 그 이유는, --(decrement)에 있다. 3번째 줄에서 b의 인자값을 --v로 해야한다. 계산된 값을 넘겨줘야된다.
//그래서 위의 코드는 Tail Call이 아니다. Tail Call을 하기 위해서 b(--v)로 해야한다.

Tail Call Optimization이란

  • Tail Call 방식으로 짜여지면 Stack을 새로 만들지 않고 이미 있는 Stack 속의 값만 대체해서 Stack을 재사용하는 방식으로 동작하도록 최적화 할 수 있다. 이러한 최적화를 Tail Call Optimization(또는 Tail Call Elimination)이라고 하며 언어의 실행 환경에서 지원해줘야 한다.
  • 크롬 브라우저에서 JavaScript의 Tail Call Optimization을 지원하지 않는다. 브라우저 지원여부는 아래 링크에서 확인 가능하다.
    출처 : https://kangax.github.io/compat-table/es6/#firefox82

Tail Recursion으로 호출 함수 횟수 줄이기

  • Tail Call로 자기자신을 호출하는 함수인 경우를 Tail Recursion이라고 한다.
  • 100번째 피보나치 값이 나오지만 오차가 있다.
  • 재귀호출을 한번으로 줄어들어 호출 횟수가 100번으로 줄었다.
function fibonacciTailRecursion(num, first, second){
  let current;
  if(num <=1){
    return num * second // second값을 곱해주어 계속 앞의 두수를 더한 값을 return한다.
  }
  // 
  current = first+second
  first = second
  second = current
  return fibonacciTailRecursion(num - 1, first, second);
}

//fibonacciTailRecursion(3,0,1)의 값은?
fibonacciTailRecursion(3,0,1)
=fibonacciTailRecursion(2,1,1)
=fibonacciTailRecursion(1,1,2) // num = 1*2

//fibonacciTailRecursion(4,0,1)의 값은?
fibonacciTailRecursion(4,0,1)
=fibonacciTailRecursion(3,1,1)
=fibonacciTailRecursion(2,1,2)
=fibonacciTailRecursion(1,2,3) // num = 1*3

//fibonacciTailRecursion(100,0,1)의 값은?
fibonacciTailRecursion(100,0,1) 
=fibonacciTailRecursion(99,1,1)
=fibonacciTailRecursion(98,1,2)
=fibonacciTailRecursion(97,2,3)
....
=fibonacciTailRecursion(1,엄청큰수1,엄청큰수2) // num = 1*엄청큰수2, 함수 호출 횟수는 100번이다.

재귀 함수로 num까지의 합을 구해보자

  • stack 에러가 난다. 그 이유는 원래 자리에서 해야할 일이 남아있기 때문에 stack에 쌓인다. 그래서 Tail Recursion방식으로 원래 자리에서 해야할 일을 남겨두지 않는 방법이 있다.
function sum(num){
  let acc = 0
  if(num === 1){
    return num
  }
  return num + sum(num - 1);
}
sum(100000) // Uncaught RangeError: Maximum call stack size exceeded

Tail Recursion 방식으로 num까지의 합을 구해보자

  • Tail Recursion으로 작성해도 stack에러가 난다. 이는 Tail Call Optimization을 지원하지 않아서 그렇다.
  • 이를 
function sumTailRecursion(num,acc){
  if(num ===0){
    return acc;
  }
  acc += num;
  return sumTailRecursion(--num,acc)
}

sumTailRecursion(100000,0) // Uncaught RangeError: Maximum call stack size exceeded

반복문으로 Stack 메모리 문제를 해결

  • 메모리는 변수만 사용하여 메모리 사용량이 낮아진다.
function sumLoop(num){
  let acc = 0;
  while(n){
    acc += n--;
  }
  return acc;
}

참고한 사이트

사용하는 경우
1. 주어진 문제가 (구조는 비슷하고) 더 작은 문제로 나뉘어 질 수 있는 경우
2. 중첩된 루프가 많거나 중첩의 정도(number of loops)를 미리 알 수 없는 경우

재귀함수의 활용(트리 구조)
1. 트리 구조에 재귀 함수를 활용
2. JSON 구조에 재귀 함수를 활용
3. DOM 구조에 재귀 함수를 활용

하노이의 탑

  • A의 막대기의 원반들을 C로 전부 옮기는 문제이다.

주의 사항

  • 한번에 움직일 수 있는 원반은 기둥 위에 놓인 원반 하나뿐이다.
  • 어떤 원반 위에 그보다 더 큰 원반을 쌓을 수 없다.
    하노이의 탑

힌트 얻기

  • 직접 원반을 그림과 같이 작은 단위일 경우를 생각하여 문제를 작게 만들어 해결하고 이후 확대 해석해보자(그림과 글 정말 존경스럽습니다. 👍😻)

문제 분해
1. hanoi(N,start,to,via): start에서 to로 via를 거쳐 총 N개의 원반을 운반할 때 각 이동 과정을 출력자
1-1. 각 원반의 출발지와 목적지가 다르다.
1-2. 중간에 경유지가 있다.
2. hanoi(3,'A','C','B')가 문제일 때,

  • hanoi(2,'A','B','C')로 그림 3번까지의 과정
  • 3번 원반을 'C'로 옮긴다. 4번 그림 코딩에서는 console.log로 출력
  • hanoi(2,'B','C','A')로 그림 5 ~ 7번 그림
function move(N, start, to){
    console.log(`${N}번 원반을 ${start}에서 ${to}로 이동`)
}

function hanoi(N, start, to, via){
    if(N===1){
        move(1,start,to)
    }else{
        hanoi(N-1,start,via,to)
        move(N,start,to)
        hanoi(N-1,via,to,start)
    }
}

function hanoiCount(N){
  console.log(Math.pow(2,N) - 1)
}


hanoi(3,'A','C','B')
//else
hanoi(2,'A','B','C') //hanoi함수의 다섯번째 줄
  //else
  hanoi(1,'A','C','B') // 1번 원반을 A에서 C로 이동
  move(2,'A','B')// 2번 원반을 A에서 B로 이동
  hanoi(1,'C','B','A') // 1번 원반을 C에서 B로 이동

move(3,'A','C') // 3번 원반을 A에서 C로 이동
hanoi(2,'B','C','A')
	//else
	hanoi(1,'B','A','C') // 1번 원반을 B에서 A로 이동
	move(2,'B','C') // 2번 원반을 B에서 C로 이동
	hanoi(1,'A','C','B') //1번 원반을 A에서 C로 이동
  • 이해가 잘 되지 않아 코딩을 일일히 분해해 봤다.
  • 재귀함수의 순서는 다음과 같다.
  1. 첫 번째 재귀에서는 맨 밑의 N번째 원반을 목적지로 옮기기 위해 위의 N-1 개의 원반을 경유지로 옮긴다.
  2. 그 다음 N 번째 원반을 목적지로 옮긴다.
  3. 경유지에 있는 N-1 개의 원반을 to로 옮긴다.

출처 : https://shoark7.github.io/programming/algorithm/tower-of-hanoi

profile
백승용
이전 포스트

HTML과 CSS

다음 포스트

JavaScriptKoans 과제

0개의 댓글