JavaScript의 기초 #4 - 재귀함수, 이중반복문

오늘은 지난 번 배운 반복문, 그 안에 다시 반복문을 사용하는 2중 반복문에 대해 알아보자.

 

그 후, 자기 자신을 호출하는 재귀함수에 대해서도 공부해본다.

1. 이중반복문

1~5까지를 출력하고 싶을 때 반복문을 사용했다.

 

for (i=1; i<6; i++) {
    console.log(i)
}

 

여기서, 1~5를 반복해 출력하는 작업을 5번 반복하고 싶을 때

 

반복문 안에 다시 반복문을 넣는 방법으로 작업을 구현할 수 있다.

 

for(i=1; i<6; i++) {
    for(j=1; j<6; j++) {
        console.log(j);
    }
}

이 코드의 결과를 콘솔에서 확인해보면 1~5까지의 출력을 5번 반복하는 것을 확인할 수 있다.

 

비슷한 예시로 2~9단까지 구구단을 출력해보자.

 

for(i=2; i<10; i++) {
	for(j=1; j<10; j++) {
        console.log(i+"*"+j+"="+i*j)
    }
}

 

내부에 있는 반복문을 한 사이클 돌린 후,

 

외부에 있는 반복문의 다음 반복을 수행하는 순으로 처리를 진행한다.

2. 스택(LIFO - Last In First Out)

재귀함수를 공부하기 전에 우선 스택의 개념을 알아야 한다.

 

스택에서 우리가 입력한 코드는 아래에서부터 쌓인다고 생각할 수 있다.

 

이후, 나중에 입력한 코드가 그 위로 쌓이고, 처리할 때는 위에서부터 처리해 나간다.

 

인터넷 브라우저에서 뒤로 가기 버튼이 이같은 방식으로 작동한다.

 

바로 전에 방문한 페이지가 가장 위에 쌓이고, 버튼을 누르면

 

가장 위에 있는 직전 방문 페이지로 돌아가게 해주는 것이다.

 

재귀함수도 이와 같은 방식으로 연산을 수행해나간다.

3. 재귀함수

재귀함수란 자기 자신을 호출하는 함수이다. 수학에서의 점화식과 비슷하다고 보면 된다.

 

1에서 100까지 더한 값을 계산하는 것에는 3가지 방법이 있다.

i) 반복문을 통해 계산하거나

function sum(n) {
    let output = 0;
    for(i=1; i <=n; i++) {
        output += i;
    }
    return output;
}
   
 console.log(sum(100));

ii) 부분합 공식을 이용하거나

function sigma(n) {
    console.log(n*(n+1)/2);
}

sigma(100);

 

iii) 재귀함수를 사용한다.

function sum2(n) {
    if (n <= 1) {
        return 1;
    }
    return n + sum2(n-1);
}

console.log(sum2(100));

이 중 가장 빠르게 연산이 되는 것은 당연히 두 번째 방법이다.

 

넣어준 매개 변수를 넣고 한 번만 계산을 하면 끝난다.

 

하지만 공식을 모를 경우, for문을 사용해 반복적으로 덧셈을 하거나, 재귀함수를 사용해야한다.

 

재귀함수를 사용한 코드를 뜯어보자.

 

주어진 경우 n = 100이므로 if문을 무시하고 바로 아래의 return문으로 간다.

 

그럼 100 + sum2(100-1) 의 결괏값을 return해줘야 하는데,

 

sum2(100-1)을 계산하면 이 return값은 99 + sum2(99-1) 이다.

 

다시 sum2(99-1)을 계산하면 이 return 값은 98 + sum2(98-1) 이고...

 

이를 1까지 반복한 값을 풀어서 써보면

 

sum2(100) = 100 + sum2(99)

= 100 + 99 + sum2(98)

= ...

= 100 + 99 + ... + sum2(2) = 100 + 99 + ... + 2 + sum2(1) = 100 + 99 + ... + 2 + 1이 된다.

 

이를 잘 보면 sum2(n)은 바로 계산되지 않고 계속 괄호안의 n을

1씩 빼주면서 옆으로 밀어냇다는 사실을 알 수 있다. 마지막엔 sum2(1)이 남게 되고,

 

이 값을 이용해 다시 sum(2), sum2(3)... 순으로 계산해나가

 

마지막에 다시 sum2(100)에 도달한다.

 

(이렇게 입력의 역순으로 연산을 처리해나가는 구조가 스택이다.)

 

 

비슷한 예시로 피보나치 수열이 있다.

 

점화식으로 표현하면 a(n) = a(n-1) + a(n-2) 인데 앞에 두 수를 더해 다음 수가 만들어지는 수열이다.

이를 코드를 통해 구현하면 다음과 같다.

function fibo(n) {
	if (n ==1 || n==2) {
        return 1;      // 첫 두 항은 1로 정의한다.
    }
  	return fibo(n-1) + fibo(n-2);

이렇게만 쓸 수 있어도 재귀함수에 대해서는 얼추 안다고 할 수 있지만, 이 코드에는 문제점이 있다.

 

숫자가 조금만 커져도 연산량이 급격히 늘어나 50항 정도만 되도

 

계산에 소모되는 시간이 크게 길어진다는 것이다.

 

이런 경우 연산량을 줄여주기위해 나온 것이 memorization이라는 개념이다.

 

단어가 생긴 것에서 추측할 수 있듯, 이는 한 번 연산한 값을 기억해두었다가 재사용하는 것이다.

 

fibo(10)을 계산하려면 fibo(9) + fibo(8)을 계산해야하는데,

 

어차피 fibo(9)를 계산하려면 fibo(8)을 계산해야한다.

 

추가적으로 뭔가 코드를 추가하지 않으면 fibo(9)를 계산하고 fibo(8)을 처음부터 다시 계산해야 하지만, 

 

memorization을 잘 이용하면 fibo(9)를 구할 때 구한 fibo(8)을 재사용해 연산량을 줄일 수 있다.

 

이를 위해서는 배열을 사용해야한다.

let arr=[1,1];    //   수열의 첫 두항
function fibo2 (n) {
	if(num[n] > 0) {
    		return num[n];     //    한 번 계산한 값을 다시 쓰게 해주는 코드
    	}

        else if (n == 1 || n == 2) {
        	return num[n] = 1;
        }

        else {
        	return fibo2(n-1) + fibo(n-2)
        }
}