[인프런]Javascript입문 - 재귀의 기초

Notice

Recent Posts

Recent Comments

Link

« 2025/05 »
일	월	화	수	목	금	토
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31

Tags more

Archives

Today

Total

관리 메뉴

Bibi's DevLog 🤓🍎

[인프런]Javascript입문 - 재귀의 기초 본문

프로그래밍/Javascript 자바스크립트

[인프런]Javascript입문 - 재귀의 기초

비비 bibi 2020. 10. 31. 21:45

* 이 글은 인프런에서 제공하는 호눅스님의 유료 강의 '쉽고 자연스럽게 배워보는 Javascript 입문 - 코드스쿼드 마스터즈 코스 레벨1'를 듣고 공부하며 정리한 글입니다. 강의 내용에 더해, 제가 필기하고 구글링한 내용이 정리되어 있습니다. 초보인 제가 이해한 대로 정리했기 때문에, 부정확한 내용이 있을 수 있음을 감안해 주시길 바랍니다. 강의를 듣고 내용을 정리한 글이기 때문에 문제가 되지 않는다는 인프런 측 답변을 받은 적이 있으나(https://bibi6666667.tistory.com/37), 저작권상 문제가 된다면 보호 모드(비공개)로 전환하겠습니다.

재귀 (recursion)란?

재귀 recursion (재귀함수) : 함수가 함수 안에서 자신을 다시 호출하는 것

var foo = function() {
	foo(); 
}

위의 함수를 실행하면?
- 무한루프처럼 foo()-foo()-foo()-... 호출만 하다가 죽는다.

카운트다운 재귀로 구현하기

카운트다운 = 10, 9, 8, 7, ... 3, 2, 1 세기.

카운트 다운 일반 버전

var countdown = function(n) {
  for (let i = n; i >= 0; i--) {
    	console.log(i);
    } 
    console.log("Fire!");
  };
  
countdown(10);

카운트다운 재귀로 구현하기 1

var countdown2 = function(n) {
    console.log(n);
    countdown2(n - 1); 
};

countdown2(10) 를 실행하면..
10 찍고 countdown2(9) 호출 - 9찍고 countdown(8) 호출 - 8찍고 countdown(7)호출 ..

❗ 위 코드는 종료 조건이 빠져 있기 때문에 무한 루프와 마찬가지로 종료가 되지 않습니다!
(10, 9, 8, 7, ... 3, 2, 1, 0, -1, -2, -3, ...)

재귀 함수는 반드시 종료 조건이 필요합니다!

재귀 함수에 종료 조건 추가

종료조건 (termination condition) : 주로 if문과 return;을 통해 재귀가 종료됨.

var countdown2 = function(n) {
  //termination condition 
  if (n <= 0) {
  	console.log("땡");
 	return; 
  } 
  
  console.log(n);
  countdown2(n - 1); 
};

countdown2(10); // 10 9 8 7 6 5 4 3 2 1 땡

재귀에는 반드시 종료조건이 필요하다.
-> return;을 사용해 함수를 끝낸다.
(n이 0이 되는 시점에서 return아래의 코드는 실행되지 않게 하기 위해!)

return; 의 두 가지 의미
1. 값을 돌려준다.
2. 함수를 끝낸다. (return;위치에서)

재귀의 2요소 (재귀를 사용할 때 주의할 점)
1. 종료조건 (반드시 종료조건이 있어야 한다.) -> if문과 return;을 사용.
2. 자기자신을 호출하며, 이 때 매개변수가 달라짐 -> countdown2(n-1); 처럼.

왜 재귀를 사용하나?

재귀를 사용하면 쉽게 풀리는 문제들이 많이 존재하기 때문입니다.
예를 들어, 알고리즘의 리스트, 트리, 그래프 순회 문제는 재귀로 푸는 게 편합니다.

재귀 vs 일반

일반 함수가 재귀 함수보다 높은 성능을 보인다.
모든 재귀 알고리즘은 일반 알고리즘으로 바꿀 수 있다.
(but.. 수학적으로 증명은 되어 있지만, 재귀를 일반으로 바꾸는 게 쉽지는 않다)

그런데 왜?

"재귀 없이 구현하면 성능이 좋아지고, 재귀를 사용하면 프로그래머의 능력이 좋아집니다."
- 누군가의 말..

코딩에서 문법을 아는 것은 굉장히 작은 비중을 차지한다.
문법보다 중요한 것은, 컴퓨터와 대화하는 "사고력" - 컴퓨팅 사고(컴퓨터적 사고, computational thinking) 이다.
이 사고력을 증진시키는 데에 재귀의 사용이 도움이 된다.

재귀로 구현하기 - 연습

a부터 b까지 정수를 더해서 리턴해 주는 함수를 만들어 보자.

var rsum = function(a, b) { 
    if (a == b) {
    	return a;
    } 
    return b + rsum(a, b - 1);
}

var x = rsum(1, 10);
console.log(x);

👉재귀에서는 보통 카운트다운 방식을 많이 사용한다.
(1부터 5까지 더하더라도, 1+2+3+4+5 가 아닌 5+4+3+2+1 로 주로 구한다)

재귀로 구현하기 - 팩토리얼

fact(3) = 3 * 2 * 1

팩토리얼 (factorial, 계승) : n! = 1부터 n까지의 모든 정수를 곱하는 것 . 3! = 3*2*1.

↓ (예외처리 없는 간단 버전)

var fact = function(n) {
    if (n === 1) {
        return n;
    }
    return n * fact(n-1);
};

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
<h1>재귀로 팩토리얼 구현하기</h1>
<script>
var fact = function (n){
    if (n < 0) { // 예외처리 : n이 0보다 작을 때.
        return NaN; // 오류를 반환.
    }
    if (n == 1 || n == 0) { // 예외처리 : n이 1이거나 0이면
        return 1; // 1을 반환.
    }
    return n * fact(n - 1);
};

// 테스트 코드 : true가 나와야 하는 코드를 먼저 짜고,
// 모든 테스트 코드가 true가 나올 때까지 코딩한다.
console.log(fact(1) === 1);
console.log(fact(2) === 2);
console.log(fact(3) === 6);
console.log(fact(0) === 1);
console.log(!fact(-1));
</script>
</body>
</html>

❗ NaN === NaN 의 결과값은? false이다!

👉 테스트 주도 개발 (TDD, Test-Driven Development)
: 테스트가 개발을 이끌어 나가는 형태의 개발론. 테스트 코드를 사용하는 개발방식?

m.blog.naver.com/PostView.nhn?blogId=suresofttech&logNo=221569611618&proxyReferer=https:%2F%2Fwww.google.com%2F

TDD(Test-driven Development) 소개

최근 화제가 되고 있는 TDD에 대한 관심이 갈수록 깊어지고 있습니다. 과연 TDD란 무엇인지 이번 ...

blog.naver.com

저작자표시 비영리 변경금지 (새창열림)

'프로그래밍 > Javascript 자바스크립트' 카테고리의 다른 글

[인프런] Javascript - 재귀의 기초2 (점화식, 피보나치수열, 다이나믹 프로그래밍 memoization) (0)	2020.11.01
[인프런]Javascript - 변수의 스코프(전역 변수, 지역 변수, 자동 전역 변수, 매개변수의 스코프, for문 안의 스코프, const와 let, 호이스팅, 클로져) (0)	2020.10.30
[인프런]Javascript입문 - 계산기 마지막 - 한 줄로 입력받아 처리 (0)	2020.10.28
[Javascript] .split(), join()을 활용해 문자열을 여러 조건으로 나누기 (0)	2020.10.28
[인프런]Javascript입문 - 계산기 - 객체 활용 (0)	2020.10.28

'프로그래밍/Javascript 자바스크립트' Related Articles

Bibi's DevLog 🤓🍎

[인프런]Javascript입문 - 재귀의 기초 본문

[인프런]Javascript입문 - 재귀의 기초

재귀 (recursion)란?

카운트다운 재귀로 구현하기

카운트 다운 일반 버전

카운트다운 재귀로 구현하기 1

재귀 함수에 종료 조건 추가

왜 재귀를 사용하나?

재귀 vs 일반

그런데 왜?

재귀로 구현하기 - 연습

재귀로 구현하기 - 팩토리얼

'프로그래밍 > Javascript 자바스크립트' 카테고리의 다른 글

티스토리툴바