재귀 알고리즘 학습
재귀함수란?
- 자기 안에서 자신을 부르면 해당 함수가 복사되어 실행되는 것
(실행컨택스트가 만들어지는 것) - 실행실행실행실행 - 리턴리턴리턴리턴 재귀함수가 호출된 곳으로 돌아감
- 수열, 규칙적이지만 복잡한 반복에 사용할 수 있다.
- 재귀 함수는 결국 반복을 위한 것이다.
풀이법
- 문제를 파악해 근본적인 수식을 찾아낸다.
- return에 수식을 적는다.
- 재귀 안 거치고 그냥 나올 수 있는 값(작은 값)을 먼저 리턴해서 그걸로 수식이 맞는지 확인해본다.
값을 리턴하지 않는 경우
- 탈출 조건
- 반복할 실행문
- 어떤 조건으로 재귀할건지
- 전위 인지 후위 인지
리턴 값으로 재귀를 하는 경우
- 다른 연산 다 재쳐두고 재귀먼저 실행됨
- 리턴을 이용한다는 것을 숫자를 들어온 인수를 역순으로 먼저 계산하는 것
- 리턴은 나중 일 - 돌아올 때 하는 것
- 파고들었다가 나오는 것까지 생각해야함
코드 실행 시점
재귀함수 실행문 이전에만 실행코드가 있다 - 파고 들어갈 때 실행됨 (전위순회)
재귀함수 실행문 이후에 실행코드가 있다 - 파고 들어갔다가 나올 때 실행됨 (후위 순회)
리턴문을 이용한 재귀
- 리턴문은 재귀함수 실행문 이후에 로직이 있는 것이므로 - 후위 순회
- 리턴을 한다는 것은 함수가 하나씩 끝날 때 반환된 값이 이전 함수 안에서 재귀함수 실행문 자리에 있게 되는 것
- 리턴을 하면 함수 각각의 실행 결과를 전달할 수 있다.
팩토리얼과 피보나치
- 팩토리얼은 전 값의 결과만 알아서 나랑 곱하면 되고,
- 피보나치는 전전과 전의 값을 알아내야한다. - 그렇기에 중복 계산이 발생한다
#프론트엔드