재귀 함수(recursive function)

재귀(再歸) - 다시 돌아온다

 

재귀 함수 -  자기 자신(함수)을 호출하는 함수를 말한다. 

 

함수가 함수를 다시 부르는 것으로 중단점을 설정하지 않으면 끝없이 자신을 호출하는 루프에 빠진다. 

 

const recursion = () => {
	
    return recursion();
}

 

이런 함수를 만들고 recursion을 호출한다면, 끝없이 자기자신을 호출하는 무한루프에 빠질 것이다.

(Runjs 같은 곳에서 하지 않길 바란다,,,,)

 

const recursion = (i) => {
	if(i<=1) return 0;
    
    return recursion(i-1);
}

그래서 i가 1이 되는 순간 멈출 수 있도록 중단점을 설정한다. (예시가 1인 것뿐 중단점은 어떻게 설정하든 상관없다.)

 

재귀함수의 가장 대표적인 예시는 팩토리얼(!)이다.

 

5! = 5*4*3*2*1 = 120

3! = 3*2*1 = 6

 

팩토리얼은 자기자신부터 1까지를 곱해나간 수를 반환한다. 

 

이를 재귀함수로 나타내면,

 

const recursion = (i) => {
	if(i<=1) return i;
    
    return i*recursion(i-1);
}

이와 같다. 

 

recursion(5)를 호출했다고 치자. 

그러면 recursion(5)는 i*recursion(i-1)을 return하므로 5*recursion(4)에서 recursion이 다시 호출된다. 

recursion(4)는 4*recursion(3)을 호출하고.... 마지막에 if문으로 1이 되면 i만 반환하게 했으므로 1을 반환한다.

 

recursion(5) = 5*recursion(4) = 5*4*recursion(3) = ... = 5*4*3*2*recursion(1) = 5*4*3*2*1 

 

이런 식이 되는 것이다!!!

 

 

재귀함수를 쓸 때 중요한 것!

1. 자기 자신을 호출한다.

2. 중단점을 설정해야한다.