[Javascript] 재귀와 스택

재귀

재귀란, 함수 내에서 어떤 함수를 호출해야하는데 호출 해야하는 함수가 자기 자신일 경우 재귀라고 말함

 

아래는 제곱근을 구하는 함수를 반복문과 재귀를 이용해서 생성

 

반복문을 이용한 a를 n번 곱하는 제곱근을 생성

function my_pow(a,n){
	
    let res = 1;
    for(let i = 0; i < n; i++){ // 1에 a를 n번만큼 곱해줌
    	res *= a;
    }
    return res;
}

console.log(my_pow(2,3)); // 2의3승인 8이 출력

 

다음은 재귀를 이용한 제곱근을 구하는 함수를 생성

function my_pow(a,n){
	
    if(n === 1)
    	return 2;
    else if(n > 1)
    	return 2 * my_pow(a,n-1);
}

console.log(my_pow(2,3));

 

위 코드에서 my_pow 라는 함수는 n === 1 일경우와 n > 1 일경우 두가지로 분기가 나뉨.

 

n이 1보다 클경우 반복적으로 인자로 받은 n을 -1 해주어서 자기자신을 호출하고 n이 1이 되면 최종적으로 함수 호출을 멈추고 2를 반환.

 

처음에 n의 값을 3으로 넘겨주었으므로 실행 순서는 아래와 같음

 

my_pow(2,3) -> return 2 * my_pow(2,2) -> return 2 * my_pow(2,1) -> return 2  

위 과정에서 함수의 절차가 함수 실행에 대한 세부 정보를 담고 있는 실행 컨텍스트에 저장됨

 

 

실행 컨텍스트에 저장된 절차들을 호출하여 최종적으로 n 을 1로 넘겨주어 2가 리턴되면 다시 역순으로 함수가 반환되어 위에 반복문을 사용한 결과와 동일하게 값이 생성됨

 

(my_pow(2,1))return 2 -> (my_pow(2,2)) return 2 * 2 -> (my_pow(2,3)) return 2 * 2 *2 

 

처음 호출한 함수를 포함한 중첩된 호출의 개수를 '재귀의 깊이' 라고함. 위 함수의 재귀의 깊이는 n으로 전달한 값 즉 3임.

 

재귀적 구조

재귀적으로 정의된 자료구조인 재귀적 자료 구조는 자기 자신의 일부를 복제하는 형태의 자료 구조임.

 

Html 과 Xml 도 재귀적 자료구조의 성격을 띔

 

 

연결 리스트

재귀적 자료구조 중 하나인 연결리스트를 사용하면 배열보다 빠르게 데이터를 삽입, 삭제 할 수 있음.

 

빈번하게 데이터의 삽입과 삭제가 있는 경우에는 배열보다 아래와 같은 연결리스트를 사용하는것이 좋음.

 

생성할 연결리스트의 프로퍼티 : val, next

• value: 현재의 값이 담긴 프로퍼티
• next: 다음 연결될 리스트를 참조할 프로퍼티  

let linkedList = {

	
    value:1,
    next:{
    	value:2,
        next:{
        	value:3,
            next:{
            	value:4,
                next:null
            }
        }
    }
}

console.log(linkedList.next)
console.log(linkedList.next.next)
console.log(linkedList.next.next.next)
console.log(linkedList.next.next.next.next)

 

 

위 결과와 같이 next에는 다음 연결 리스트의 프로퍼의 참조가 연결되어 있어서 next 프로퍼티를 이용하여 빠르게 참조를 끊고 추가할 수 있음

 

리스트를 분해

secList = linkedList.next.next;

console.log(secList);

 

리스트의 2번째요소의 next가 참조하는 3번째 연결 리스트부터 값에 들어옴

 

 

맨 앞에 요소를 추가 

linkedList = { value:0, next:linledList };

console.log(linkedList);

 

맨앞에 값을 0으로 가지고 있는 연결 리스트가 추가됨

 

 

중간의 요소를 제거

linkedList.next = linkedList.next.next;

console.log(linkedList);

 

값을 1로 가지고 있는 연결 리스트가 제거됨

 

 

참조: https://ko.javascript.info/recursion