- 정의
어떤함수가 자기자신을 호출하는 함수- 장점
알고리즘이 재귀로 표현하기에 자연스러울 경우, 프로그램의 가독성이 좋음.- 단점
값이 리턴되기 전까지 호출마다 call stack을 새로 생성하므로, 메모리를 많이 사용함.
재귀함수 복습으로 fibonacci수열을 재귀함수로 구현을 해보겠습니다.
피보나치는 수열 종류 중 하나이다.
1 1 2 3 5 8 13 21 34....
앞에 있는 숫자와 그 앞에 있는 숫자와 더한 것을 나열하는 것이다.
1+1 = 2
2+3 = 5
3+5 = 8
5+8 = 13
..
이런 식으로
출처: https://marobiana.tistory.com/80 [Take Action]피보나치수열에 대해 잘 설명을 잘 해놓은곳입니다. 잘모르겠으면 클릭 -> 피보나치에 대해서 잘 모르겠으면 클릭
function fibo(n) {
if(n < 0) {
return -1;
} (종료조건 만약 음수의 값이 들어온다면 -1을 리턴 이상한값이 들어올수 있기때문에 종료조건을 걸어주었다.)
if(n < 2) {
return n
}(기반조건 만약 n의 값이 1보다 작다면 n을 리턴해라. 이조건으로 재귀함수를 탈출할것이다.결과적으론 0,1값만 들어올것이다. 기반조건을 세우는게 재귀함수에 포인트!)
return fibo(n-1) + fibo(n-2);(재귀식)
}
-----------------------------------------------
fibo(4) // 3저는 처음 이 코드를 봤을때는 매우 짧은코드여서 쉬워보였지만 코드의 동작순서를 보고 난 후에 멘붕에 빠졌습니다.
코드에 대해서 내가 설명을 하는것보다 그림으로 잘 설명이 된거 있어 첨부하겠습니다.
밑의 그림에서 숫자 순서대로 그림을 집중하고 보시면 빠른 이해가 될겁니다.
그래도 만약 이해가 안된다면 이 블로그 가서 피보나치 재귀함수에 대해서 설명을 보신다면 이해가 빠르게 될겁니다.
그림에 대한 출처를 남기겠습니다. 출처
그래도 간략하게 설명을 하자면(내용설명)
위의 그림이랑 같이 보세요!
fibo(4)라는 함수를 실행을 했을때 4는 1,2보다 크기 때문에 재귀식으로 바로 넘어 갈것이다.
여기서 포인트는 왼쪽 실행식이 끝나고 오른쪽 실행식이 실행된다.
예를 들어 return fibo(3) + fibo(2) 가 있다면 fibo(3)이 다 실행 된 후 fibo(2) 함수가 실행된다.
(1) // 설명을 하기 편하게 하기위해 위의 그림의 번호랑 같은번호를 적음.
return fibo(4-1) + fibo(4-2) // 재귀식 //쉽게 설명하게 위해 fibo(4-2) + fibo(4-1)로 표현 n: 4이기때문에
밑에서 적을때는 바로 fibo(3) + fibo(2) 적을것이다.
return fibo(3) + fibo(2) // 왼쪽함수부터 실행 후 오른쪽 함수 실행!
그렇다면 fibo(3) 실행!
3 또한 1,2보다 크기 때문에 재귀식으로 바로 넘어 갈것이다.
(2)
return fibo(2) + fibo(1) // 재귀식fibo(2) 실행!
기반조건에 해당되지 않기 때문에 다시 재귀식으로!
(3)
return fibo(1) + fibo(0) // 재귀식fibo(1) 실행!
기반조건에 해당되므로 1이 리턴 될것이다.
(4)
if(n < 2) { return n} //기저조건=====================================================
밑에 설명중에 (3) 이렇게 되어있다면 위에서 표시해두었던 식의 숫자입니다.
(3)이면
(3)
return fibo(1) + fibo(0) // 재귀식=======================================================
fibo(1)에 대한 리턴값이 1이고 그다음 fibo(0)을 실행할것이다.
fibo(0) 또한 기저조건을 만나 0을 리턴할것이다.
(3)의 리턴값은 1 + 0 = 1 이 될것이고 이것은 fibo(2)를 실행했을때 리턴값이다.
재귀식 (2)에서 fibo(2)의 리턴값이 1이고 fibo(1)의 리턴값은 위에서 설명을 했듯이 1이다.
그 결과 fibo(2) + fibo(1)을 했을경우 리턴값은 2이고 이값은 fibo(3)의 리턴값이다.
fibo(3)에 대한 실행식이 끝났기 때문에 fibo(2)에 대해서 함수가 실행이 될 것이다.
fibo(2)에 대해서는 그림을 보면서 생각을 한다면 이해가 될 것입니다!
이번주에 대해서 간단히 나를 돌아 본다면
- 지난주보다 집중도가 많이 떨어진것 같음
한가지에 잘 집중을 잘하지 못함.
다음주에는 좀 나아졌으면 좋겠다.- 어제 코드스테이츠 pass-me 시험이 끝났고 다음주부터는 immersive코스가 시작된다.
- 이번주 남은날들은 복습위주로 하고 부족했던 부분에 대해서 조금 공부를 하고 블로깅도 해야겠다.
- 재귀함수는 어렵지만 계속 보니깐 보인다(?)
내일도 블로깅을 한다면 재귀함수에 대해서 써봐야겠다.
