재귀함수

자기 자신을 호출하는 함수이다

간단한 예를 들면

인자값으로 넣은 값부터 1까지 찍어주는 함수이다
0보다 작거나 같지 않다면
foo 함수에 num - 1 값을 다시 넣어 실행시켜준다

0보다 작거나 같다면 Done 출력 후 함수를 종료한다

조금 더 어렵게 작성을 해보면

위 함수는 입력한 값부터 1까지 더한 값을 출력하는 함수입니다

작동 순서를 이야기 해보자면

1. 첫번재 인자값은 3
   반환되는 값은 num이 1이 아니기 때문에 3 + foo(2) foo함수의 값이 리턴 되지않았기 때문에 기다립니다
2. 두번째 인자값은 2
   반환되는 값은 num이 1이 아니기 때문에 2 + foo(1) 마찬가지로 foo 리턴을 기다립니다
3. 세번째 인자값은 1
   num은 1이기 때문에 return 1을 해줍니다
4. 두 번째에서 리턴한 foo(1)의 값이 리턴이 되었기 떄문에 2 + 1 값인 3을 리턴해줍니다
5. 첫 번째에서 리턴한 foo(2)의 값이 리턴이 되었기 떄문에 3 + 3 값인 6을 리턴해줍니다

이와 같은 방식으로 작동이 됩니다

조심해야할 점

• 종료 지점을 만들어 주어야한다
• 반환 값을 올바르게 주어야한다
• 반환하는 것을 잊지 않는다
• Stack overflow가 나지 않도록한다

Helper 메소드 재귀

홀 수만 얻을수 있는 collectOdds 함수이다
내부에 재귀함수를 이용하여 홀수만 result에 추가하여 return 하는 방식이다

Pure 재귀

위의 Helper 재귀를 순수 재귀로도 만들 수 있습니다

위 재귀는 다음과 같이 생각하면 쉽게 이해가 되실겁니다

파라미터인 arr의 0번째 인덱스를 확인하고 홀수라면 newArr배열에 추가를해줍니다
추가한 newArr에 concat메서드를 사용하여 collectOddValues(arr.slice(1))를 실행시켜줍니다
이와 같이 실행을 하게 된다면
0번째 인덱스가 홀수라면 newArr에 값이 들어가있고 짝수라면 빈 배열을 반환하게 될겁니다
그렇게 9까지 도착을 하게 되면
[1] + [] + [3] + [] + [5] + [] ... 이런식으로 반환이 되어 concat메서드로인해 배열이 합쳐져 [1,3,5,7,9] 값이 나오게 됩니다.

피보나치 문제

피보나치 수열에서 입력한 값 번째의 값은 무엇인지 구해야하는 문제

function fib(num){
	if(num <= 2) return 1
	return fib(num-1) + fib(num-2)
}

fib(4) //3
fib(10) // 55
fib(28) // 317811

F_n = F_n -1 + F_n -2 다음 식을 이용하여 풀면 간단하게 가능하다