재귀(Recursion)

재귀는 간단하게 요약하면 어떤 함수가 자기 자신을 호출하는 순간을 의미한다. 조금 더 비유하자면 아래의 이미지와 같다.

재귀는 어떠할 때 사용하는게 좋을까?

Google에 재귀함수 성능을 찾아보면 대부분의 사람들이 재귀함수 대신 for 반복문을 쓰는게 훨씬 효과적일 거라고 말한다. Stack이라는 메모리 공간을 이용하기 때문에 메모리의 제한이 있는경우 Stack overflow가 뜨면서 결국 답이 없는 상황까지 온다고 한다.

즉, 재귀함수는 메모리를 많이 먹고 반복문에 비해 느리다. 그런데도 쓰는 이유는 무엇일까?

1. 구조가 비슷한 주어진 문제가 더 작은 문제로 나뉘어 질 수 있는 경우

2. 중첩된 루프가 많거나 중첩의 정도를 미리 알 수 없는 경우

두가지로 나뉘게된다..

재귀 함수 Base

일반적인 상황에서 재귀 함수의 템플릿은 다음과 같다.

function recursion(val1, val2...){

//탈출지점을 지정한다 = 문제를 더이상 쪼갤 수 없는 경우
	if(더이상 쪼갤수 없을경우){
		return 문제의 해답
	}
    
//기본 조건(해당하는 일이 일어난다면)
// return 이런답

	
//그렇지 않은 경우 재귀

  return 더 작은 문제로 새롭게 정의된 문제
  
}

재귀함수는 3가지 특성을 갖는다

1. 종료조건(탈출지점)

종료 조건은

2. 기본 조건

3. 재귀

일반적인 재귀 함수에서는 마지막에 return에 연산식이 필요하다.(n + func(n - 1)

꼬리 재귀인경우에는 매개변수로 필요한 연산을 전달한다(func(n-1 n+ acc))

1.Factorial

어떤 수를 입력받아 N!(N factorial 곱셈) 값을 리턴해야 하는경우..

function fac(n) {
//탈출 지점을 만든다.
// n이 1보다 작거나 같으면 1을 반환한다.

  if(n <= 1){
    return 1;
  }
//n 부터 1까지 계속 곱해준다.
  return n * fac(n - 1)
}

예시(

fac(5)?

5 * fac(5 -1)

5 * 4 * fac(4 - 1)

5 * 4 * 3 * fac(3 - 1)

5 * 4 * 3 * 2 * fac(2 - 1)

5 * 4 * 3 * 2 * 1 (n <= 1)

해당 코드는 fac(n-1)을 호출하고, 콜 스택이라는 어떠한 대기중인 공간으로 가게된다. 자료구조의 stack구조라고 생각하면 좋은것 같다. 스택은 FIFO 구조인데 가장 최근에 들어온 녀석이 가장 먼저 나가는 형식이다.

재귀함수에서 탈출지점을 만들고, 조건에 만족하면 재귀해주는 구문(Statement)에 의해서 call stack이라는 공간에 뿌려놓은걸 다시 회수한다.