algorithm - 재귀함수

재귀함수

재귀함수는 어떤 함수 내부에서 자기 자신을 부르는 함수이다.

어떤 측면에서는 조건을 만족하기 전까지 무한히 반복하는 while 문과 닮아있다.

재귀함수는 두 가지 조건을 충족해야 한다.

• 자기 자신을 함수 내에서 반드시 return 해야 한다.
• 무한히 실행되는 것을 방지하기 위해 종료 조건문을 작성해야 한다.

 

// 재귀함수 예시

function recursion () {
  if()		// 종료 조건문
  recursion() // 자기자신 실행
}

어떤 면에서는 이게 말이 되는 문법인가 싶긴 하지만, 조건을 추가해주면 가능하다.

 

직접 만들어본 문제

전달인자 s(5)에 대해 반복적으로 1씩 차감한다고 할 때, 's<0' 이하가 되기 위해서 몇번을 반복해야 하는가

// 재귀함수 예시

function recursion (s) {
  if(s < 0) return 0 	// 끝내는 조건 s < 0 
  			// 이때 return 값이 0 인 이유는 
                        // 실제 리턴되는 값에 포함시키지 않기 위함
  return recursion(s-1) + 1 // 반복할 때마다 +1씩 리턴값 추가
}
recursion(5)	// 6

 

재귀 함수 예시로 자주 보이는 팩토리얼 문제

// 재귀함수 팩토리얼 예시

function recursionFactorial (s) {
  if(s < 1) return 1	// 곱셈이므로 return값은 1
  return s*recursionFactorial(s-1)
}
recursionFactorial(5)	// 120