재귀 함수
함수 안에서 함수 자기자신을 호출하는 방식
재귀 함수는 반복적인 처리를 위해 사용한다.
- 재귀 호출을 사용하려면 반드시 종료 조건이 있어야한다.
탈출 조건(종료 조건)이 존재하지 않는다면, 함수한 무한 호출되어 stack overflow(스택 오버플로) 에러가 발생한다.
재귀 함수 장점
기존 반복문에 비해 코드를 효율적으로 짤 수 있다.
ex) 피보나치 수열
피보나치 수열 with 반복문
function fibo(n){
let arr=[];
if(n>0){
arr[0] = 1;
arr[1] = 1;
for(let i=2;i<n;i++){
arr[i] = arr[i-1] + arr[i-2]
}
}
return arr[arr.length-1]
}
fibo(10)피보나치 수열 with 재귀 함수
function fibo(n){
if(n<=1){
return n;
}
return fibo(n-1)+fibo(n-2);
}
fibo(10)재귀 함수의 단점
- 연산이 느리다(많은 연산 필요)
피보나치를 재귀 함수를 통해 구현할 때,
위와 같이 이미 구한 fibo(1), fibo(0) 이더라도 계속해서 연산에 해당 과정이 들어간다.
따라서 피보나치의 경우 n이 클수록, 중복되는 수가 많아지고, 연산도 기하급수적으로 늘어나게 된다.
이러한 재귀 함수의 단점을 보완하기 위해 동적 프로그래밍을 사용한다.
- 재귀 함수의 단점으로 인해 현재 실무에서는 재귀 함수를 거의 사용하지 않는다고 한다.
[백준] 팩토리얼(10872)
문제 링크
https://www.acmicpc.net/problem/10872
코드
let input = require('fs').readFileSync('/dev/stdin').toString();
function factorial(n){
if(n<=1){
return 1;
}
return n*factorial(n-1);
}
console.log(factorial(input))풀이: 반복되는 부분 찾기
let input = require('fs').readFileSync('/dev/stdin').toString();
let num = 1;
for(let i=1;i<=input;i++){
num=num*i
}
console.log(num)for문으로 팩토리얼을 풀어보면 num=num*i가 반복되는 것을 확인할 수 있다.
num에는 곱한 값이 계속 업데이트되고, i는 단순히 1씩 증가하는 수이다.
따라서 이를 팩토리얼로 변환시키려면, i 변수처럼 단순히 1씩 증가하는 부분을 return을 통해 재귀 호출하면 된다.
[백준] 피보나치 수 5(10870)
문제 링크
https://www.acmicpc.net/problem/10870#### 코드
let input = require('fs').readFileSync('/dev/stdin').toString();
function fibo(n){
if(n<=1){
return n;
}
return fibo(n-1)+fibo(n-2);
}
console.log(fibo(input));풀이: 반복되는 부분 찾기
피보나치 수열은 다음과 같은 규칙을 따른다.
0 => 1 => 1 => 2 => 3 => 5 => 8
내가 4의 위치에 있다면 2의 위치에 있는 숫자 1과 3의 위치에 있는 숫자 2를 더한 값인 3을 결과로써 나타내야 한다.
이를 수로 나타내면
내가 n이라고 했을 때,
n = (n-1) + (n-2)가 된다.
여기서 핵심은 탈출 조건인데, n이 0이거나 1인 경우, return 값으로 n을 반환시켜, 초기 값을 세팅시켜준다.
[구름] 계단 오르기(10870)
문제 링크
https://level.goorm.io/exam/43083/계단-오르기/quiz/1
코드
// Run by Node.js
const solution = (data) => {
function climb(n){
if(n<=1){
return 1;
}
return climb(n-1)+climb(n-2)
}
console.log(climb(data))
}
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
let data
rl.on("line", function(line) {
data = line;
rl.close();
}).on("close", function() {
solution(data);
process.exit();
});풀이: 규칙 찾기
n칸을 올라가는 경우의 수
- 1칸: 1 (1)
- 2칸: 1+1, 2 (2)
- 3칸: 1+1+1, 1+2, 2+1 (3)
- 4칸: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 (5)
피보나치 수열과 같은 규칙이 적용된다는 것을 알 수 있다.
n = (n-1) + (n-2)
하지만 약간의 예외를 적용해 주어야 하는데,
0칸의 경우 경우의 수가 0이여야 하지만, 재귀 함수를 위해서는 0칸도 return 1을 주어야 한다.
문제 조건이 n은 30 이하의 양의 정수 이므로 0칸에 return 1을 반환하는것은 크게 의미를 두지 않아도 될 듯 하다.
if(n<=1){
return 1;
}