[TIL]재귀함수에 대한 간단정리

Violet Lee·2020년 10월 18일

javascript

목록 보기

16/24

재귀란

"자신을 정의할때,자기자신을 재참조하는것"

을 말한다.

recursive vs Iterative
보통 recursive와 Iteraive가 많이 비교되곤한다. Iterative는 반복적인 뜻을 담고있다.
즉 우리가 사용하는 for문이나. forEach문 같은 반복연산을 의미한다.

stack

재귀호출을 이용하기위해서는 스택이라는 자료구조를 먼저 살펴보는게 좋다. 왜냐면 우리의 컴퓨터는 호출스택이라고 불리는 스택을 사용해 함수를 실행하기떄문이다.

호출스택은, 일반적인 프로그래밍에서도 중요하지만, 재귀를 사용할때 더욱 중요하다고 한다..
스택은 선입후출이라서 LIFO의 구조이다. <- 즉, 자료의 입출력이 언제나 목록의 한쪽 끝에서만 일어난다.

우리가 만약에 , 매일 아침에 그날 할일을 하나씩 적어서 포스트잇으로 붙여넣는다고 생각해보자.
다만, 포스트잇을 여러군데 붙여놓을순 없고, 오로지 한곳에만 겹쳐서 붙여넣을수있다.

ex) 1. 운동하기 2.숙제하기 3.시장보기

이제 가장 위에 적힌 할일을 해결하다보면, 위에서부터 포스트잇을 뗄 수있다.
맨앞에 적힌 할일은 '3. 시장보기'이다.
시장보기를 완료하고나면, 맨위의 포스트잇을 제거하고, '2.숙제하기'를 할수있다.
만약 우리가 맨위의 '3. 시장보기'를 완료하지 못하면, 다음 할 일은 할 수없게 된다.

그러니까 우리는, 맨 처음에 쓴 '1.운동하기'를 하기위해선, 시장을 보고 포스트잇을 제거하고, 숙제를 하고 포스트잇을 제거해야만 한다.

이때, 할일을 적어 포스트잇을 붙이는것을 push라고한다. 그렇다면 떼어내는일은 pop이겠지?

그러니까 포스트잇을 붙이고나면, 우리는 그 위에만 계속적으로 포스트잇을 붙일수있고, 아래에 붙이는것은 불가능한 것과 같다. 아래에 붙이려면, '붙이길 원하는 곳까지 포스트잇을 떼어내어 제거한후' 다시 붙이는 방법밖에는 없다.

~일반적인 재귀함수의 템플릿~

function recursive(input1, input2){
	if(arr의 길이가 0인경우){ //재귀의 기초(base case: 기반조건) : 문제를 더이상 못 쪼갤경우
	 	return 단순한 문제의 해답;
	}
	//recursive case(즉, 재귀): 그렇지 않은경우
	return 더 작은 문제로 새롭게 정의된 문제.
	//ex) someValue + recursive(input1Changed, input2Changed, ..)
	//ex) someValue + recursive(input1Changed, input2Changed, ..)
}

1) factorial로 알아보는 재귀함수.

function fac(n){

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

=> 팩토리얼 함수 흐름

(1). 먼저 호출하고, 리턴할 값을 만드는 과정.

우리는 숫자 5를 넘겨서 함수를 호출한다.

   ex) fac(5)

인자가 넘어가면, 함수가 동작한다. if문을 넘어가고, 재귀 발생한다.
첫번째 함수실행: 정수 5와, fac(5-1)이 곱해진 결과를 반환한다.

   -> return 5*(5-1);

fac(4)가 동작할때, if문을 다시 넘어가고, 재귀가 일어난다.
두번째 함수실행: 정수 4와 fac(4-1)이 곱해진 결과를 반환하게된다.

   -> return 4*fac(4-1);

fac(3)이 동작할때, if문을 다시 넘어가고, 재귀가 일어난다.
세번째 함수실행: 정수 3과 fac(3-1)이 곱해진 결과를 반환하게된다.

   -> return 3*fac(3-1);

fac(2)가 동작할때, if문을 다시 넘어가고, 재귀가 일어난다.
네번째 함수실행: 정수 2와 fac(2-1)이 곱해진 결과를 반환하게된다.

   -> return 2*fac(2-1);

마침내 fac(1)이 동작할때, 1은 우리의 기반조건이므로, if문에 걸려서, 먼저 1을 반환하게된다.

   -> if(n===1) { return 1; }

1을 반환하기 전까진, 단순히 함수는 '리턴을 마친것'이다.
재귀는 단순히 '중첩된 호출'이기 때문에,
모든 중첩된 함수 중, '가장 내부에 중첩된 함수'가 가장 먼저 반환될것이다.

(2). 만든 '리턴할 값'을, '가장 내부에 중첩된 함수'순으로 '반환'하는 과정.

여기서 가장 먼저 리턴을 마친값은 fac(1)이다. 그러므로 1이 가장 먼저 반환될것이다.
다음으로 fac(2) => 2xfac(1) === 2x1=2가 반환.
다음으로 fac(3) => 3xfac(2) === 3x2=6이 반환.
다음으로 fac(4) => 4xfac(3) === 4x6=24가 반환.
다음으로 fac(5) => 5xfac(4) === 5x24=120이 반환.

즉, 한번에 눈에 들어오게 구조를 짜면 다음과 같다.

factorial(5) = return 5xfac(4)
factorial(4) = return 4xfac(3)
factorial(3) = return 3xfac(2)
factorial(2) = return 2xfac(1)
factorial(1) = return 1;
//여기서 기반조건이 충족된다. 재귀함수는 안에서부터 바깥으로 값을 반환해나간다.!
factorial(1) = return 1; => output=1;
factorial(2) = return 2xfac(1) => output = 2x1 = 2;
factorial(3) = return 3xfac(2) => output = 3x2 = 6;
factorial(4) = return 4xfac(3) => output = 4x6 = 24;
factorial(5) = return 5xfac(4) => output = 24x5 = 120;

❗만약 위의 예제에서, 기반조건을 만들어주지 않는다면 어떤일이 발생할까.?

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

위 코드는 언뜻 보기엔 그럴싸해 보이지만, 심각한 오류를 가지고있다.

▶Uncaught RangeError: Maximun call stack size exceeded
 at fac (<anonymous>:1:20)
 .
 .
 .

위 코드는 실제로 실행해보면 브라우저는 지구 끝까지 갈 기세로 코드를 계속적으로 실행하다가, 어느 시점에 저런 에러를 출력하고 멈춰버린다.. 즉, 최대 호출 스택 사이즈가 초과되었다는것이다.
이 부분이 바로 우리가 재귀함수를 사용할때 가장 유의해야하는 부분이다.

재귀 함수를 작성하여 호출시, 함수는 자기 자신을 계속해서 호출하게된다. 이때, 특정조건이 되었을때,
'재귀호출을 종료하는 문장'이 '반드시 하나이상 존재'해야하는데, 이렇게 재귀호출을 중단시키는 문장을
Base Case or Termination Case 라고 한다.

위의 팩토리얼 코드는 base case가 없으므로 fac(5), fac(4), fac(3), fac(2), ... , fac(0), fac(-1), fac(-2) ... 이렇게 음수의 영역까지 계속해서 호출하며, 순차적으로 스택에 쌓을것이고, 어느순간 정해진 메모리용량을 초과해버리게 되서, 위와 같은 에러메시지를 출력하게되는것이다..!

이제 위 코드에

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

이렇게 기반조건을 추가해준다. 이 이유는, 호출시, n이 if문의 조건에 부합하는값이 나올때 함수를 종료하여,
안의 가장 내부의 함수들부터 그 값들을 리턴하게 되는 원리이기 때문이다.

2) 문자열을 거꾸로 뒤집는 예제

function revStr(str){
	if(str === ''){
		return '';
	}
	return revStr(str.substring(1)+str[0]);
}
revStr('cat'); //tac

=> 문자열뒤집기 함수 흐름

(1). 먼저 호출하고, 리턴할 값을 만드는 과정.

처음에 함수 호출시, 문자열 'cat'을
'substring을 이용해서 1번째인덱스부터 자른것' + '0번째문자열'을 하여 'at' + 'c'을 리턴한다.
두번째 함수호출시, 문자열 'at'를(1번째 인덱스부터 자른 문자열이 저장됐으므로 'at')
'substring을 이용해서 1번째 인덱스부터 자른것' + '0번째문자열'을 하여 't'+'a'를 리턴한다.
세번째 함수호출시, 문자열 't'를(그 다음으로 또 1번쨰인덱스부터 자른 문자열이 '계속해서' 저장됨.)
'substring을 이용해서 1번째인덱스부터 자른것' + '0번째문자열'을 하여 ''+'t'를 리턴한다.
네번째 함수호출시, 문자열 ''를 substring으로 자른 1번째 인덱스부터의 문자열 ''+ 0번째문자열인 ''을 더한값이 리턴되어 기반조건에 부합될것이다.
//이제 기반조건인 ''(문자열의 길이가 0일때)에 부합하므로, 저장된 '리턴값'들을 반환해줄 차례이다.

(2) 리턴값이 반환되는 순서는, '가장 내부에 중첩된 함수값'이 제일먼저 반환될것이다.

먼저 str의 길이가 없어질때까지 substring해가면서 자른 문자열 ''이 가장 먼저 반환될것이다. '' => ''
그 다음으로 내부에 중첩된 함수인 세번째 함수가 호출되어 => ''+''+'t' => 't'
그 다음으로 내부에 중첩된 함수인 두번째 함수가 호출되어 => 't'+'a' => 'ta'
그 다음으로 내부에 중첩된 함수인 첫번쨰 함수가 호출되어 => 'ta'+'c' => 'tac'

즉, 한번에 눈에 들어오게 구조를 짜면 다음과 같다.

revStr('cat') return revStr('at')+'c'
revStr('at') return revStr('t')+'a'
revStr('t') return revStr('')+'t'
revStr('') return '';
//여기서 기반조건이 충족된다. 재귀함수는 안에서부터 바깥으로 값을 반환해나간다.!
=>revStr('') => return ''; => output='';
=>revStr('t')=> return 't'; => output=''+'t';
=>revStr('at')=>return 'ta'; => output='t'+'a';
=>revStr('cat')=>return 'tac'; => output='t'+'a'+'c';