2-2[자료구조/알고리즘]재귀함수
재귀란
어떤 문제를 동일한 구조의 더 작은 문제로 나눠 각각을 해결함으로써 전체를 해결하는 방법
어떤 함수가 스스로를 호출하는 것
키워드 : 동일한 구조 + 더 작은 문제
재귀적 사고
- input - output
- input을 기준으로
1)경우의 수를 나눈다
2)반복되는 동일한 구조의 해결방법을 찾는다- 2-1 중 base case (탈출 조건)을 구현한다
- 2-2 함수로 만들어서 recursive case를 구현한다
function arrSum(arr){
//1. input : [숫자] ouput : sum
//2-1. (1) base case: arr =[] (2) recursive case: 이외
//2-2. arr[1] + arrSum(arr.slice(1))
//Base Case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초)
if(arr의 길이가 0인 경우) {
return 0;
}
//Recursive Case : 그렇지 않은 경우
문제를 더 이상 쪼갤 수 없는 경우
head : 배열의 첫 요소
tail : 배열의 첫 요소만 제거된 배열
return head + arrSum(tail);
}
재귀 함수의 템플릿
function recursive(input1, input2, ...){
//**Base Case: 문제를 더 이상 쪼갤 수 없는 경우 **
if(문제를 더 이상 쪼갤 수 없을 경우){
return 단순한 문제의 해답;
}
//recursive Case
//그렇지 않은 경우
return 더 작은 문제로 새롭게 정의된 문제
someValue + recursive(input1Changed, input2Changed, ...)
someValue + recursive(input1Changed, input2Changed, ...)
}
factorial
function fac(n){
if(n===1){
return 1
}
return n * fac(n-1)
}
가장 내부에 있는 함수부터 실행되어서 값을 전달받는다
재귀함수의 작동 원리
본인 안에서 다시 호출된 함수는 콜스택에 쌓인다
5를 넣으면 4를 넣어서 호출되고 [스스로 복사해서 콜스택에 쌓는다] : callstack은 debugger로 확인 가능
4를 넣으면 3을 넣어서 호출되고
3을 넣으면 2를 넣어서 호출되고
2를 넣으면 1을 넣어서 호출된다
Author And Source
이 문제에 관하여(2-2[자료구조/알고리즘]재귀함수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@nikki/자료구조알고리즘재귀함수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)