sum 함수 만들기 (재귀, 꼬리 재귀, 번역한 for문)

https://jootang2.tistory.com/172

프로그램이란...?

이어서 오늘은 함수에 대해서 배웠다.

 

그리고 앞으로 이 수업을 들으면서 진행하는 방향도 알았다,

 

Q. 1부터 10까지 더하는 함수를 작성해라

if(1){
    let acc = 0;
    for(let i = 1 ; i <= 10; i ++) acc +=i;
    console.log(acc);
}

 

보통 제일 먼저 떠오르는 방법이다.

 

하지만 이 방법은 이렇게 간단한 문제일 때나 쓸 수 있다.

Json parse나 stringify를 for문으로 만들 수 있을까?

만들 수 있지만 sum 함수를 만드는것처럼 바로 만들지는 못할 것이다.

 

그래서 우리는 복잡하고 어려운 for문을 만드는 방법을 Programming101 수업에서 배우면서 훈련한다.

 

복잡한 for 문을 짜는 방법

1. 재귀로 코드를 작성한다.
2. 꼬리 재귀 최적화된 코드로 작성 (tail recursive optimization)
3. 꼬리 재귀 함수를 기계어로 for문으로 번역

 

 

1. 재귀로 코드 작성

 

우리는 모든 경우에 대해서 생각할 수 없다. 그건 컴퓨터에게 미뤄놓자.

그래서 우리는 반복되는 패턴을 찾고, 한가지 경우에 대해서만 짜면 된다.

귀납적 방법으로 짜야한다.

 

sum(10) = 10 + sum(9)

sum(9) = 9 + sum(8)

...

이렇게 볼 수 있다.

 

재귀함수로는 다음과 같이 코드를 작성할 수 있다.

const sum = v => v > 1 ? v + sum(v - 1) : 1;

 

현재 코드의 문제점
 a() -> b() -> c() -> d() -> ........  : d가 처리되어야 c가 처리되고, c가 처리되어야 b가 처리되고....  
 이 과정이 길다고 생각하면 컴파일러 혹은 스크립트엔진이 보기에는 비정상적인 작업으로 보기 때문에 죽는다. (stackOverFlow)

 

해결 방법

함수의 return point를 인수인계 해주면 a() ... z() , z()에서 바로 a()로 돌아오기 때문에 그 사이에 있는 b(), c(), d()는 대기하지 않는다.

 

현재 코드에는 sum(v - 1)로 돌아왔음에도 '+' 라는 할 일이 남아 있다. 이를 해소하기 위해서는 인자로 넘기면 된다.

const sum = (v, acc = 0) => v > 1 ? sum(v - 1 , acc + v) : acc + 1;

 

만약 함수가 다녀와서 할 일이 있다면 함수의 인자로 바꿔주면 된다.

 

2. 꼬리 재귀 함수로 변환

현재 코드 문제점
 * 현재함수는 acc에 기본 값이 없다면 undefined 발생
 * 합계를 위한 값을 초기화 시켜줘야 한다는 말, 하지만 사용자에게 노출하면 안됨

 

 const _sum = (v, acc) => v > 1 ? _sum(v - 1 , acc + v) : acc + 1;
 const sum = v => _sum(v, 0);

 

tail recursive optimization을 지원해주는 언어는 stack을 쌓지 않고 호출이 가능

하지만 지원해주지 않는다면 for문으로 변환해야 한다.

 

위 코드에서 stackOverFlow 에러가 나오면은 답이 없다.

코드는 잘못된 곳이 없으니까...

 

그래서 for문으로 짜야 한다.

 

3. 기계적으로 for문으로 변환

let acc = 0; // 저장소 - 스토리지
const v= 10; // 상수 - 특정 컨텍스트 : 해결하려는 문제 하에서 미리 주어진 값

for(let i = v; i > 1 ;i --) acc += i;
// i : 제어 변수 : 카운터
acc += 1;

* 패턴 1 : v와 acc (인자) 정확하게 제어문에서 변수로 변환
 * 초기값 10은 주어진 조건으로 변환
 * for문의 조건 = v>1과 일치
 * i -- 는 v - 1과 일치
 * for 본문에서의 코드 : acc + v 와 일치 
 * acc + 1 => acc += 1과 일치

 

 

이와 같은 방법으로 어려운 함수를 for문으로 작성할 수 있다.

 

 

 

다음 시간에는 1차원 배열을 모두 더하는 함수를 만들어보자.

 

그리고 더 나아가 Json parser 와 html parser도 만들게 될 예정이다.

 

ref : https://www.youtube.com/watch?v=0lAsf19iE2g&t=5339s