재귀함수

재귀함수는 진짜 너무 어려운 것 같다. 가벼운 마음으로 시작했다가 하루 종일 고통 받았다. 혹시나 뭔가 묘수가 있나 싶어서 재귀함수 잘 만드는 법 같은 걸 검색해봐도 별로 와닿질 않는다.

이전에 이렇게 재귀함수를 만들다가 고통 받고 결국 적당히 넘어갔고, 보통은 반복문이 더 효율적이라거나 잘 안 쓰인다거나 하는 위로 아닌 위로를 받은 기억이 새록새록 떠올랐지만, 못 하는 걸 또 다시 못 하고 넘어갈 수는 없다 싶어서 한참 붙잡고 있었다.

그래서 어떤 문제?

전부 정수로 이루어진 이진트리가 주어지고 루트 노드에서 시작해서 리프 노드에 이를 때 까지 값을 전부 더한 뒤, 각각의 리프노드에서 나온 값을 맨 왼쪽 가지부터 순서대로 하나의 배열에 담아 반환하면 된다.
어째 말로 설명하는 것부터 어렵다.

Code

/*
 * 주어진 이진트리의 구조
 */
class BinaryTree {
	value: number;
	left: BinaryTree | null;
	right: BinaryTree | null;

	constructor(value: number) {
		this.value = value;
		this.left = null;
		this.right = null;
	}
}

/*
 * 노드를 지날 때 마다 더한 값을 저장하고,
 * 리프노드에 도착하면 지금까지 저장 된 값을 배열에 담아 반환하는 보조 함수
 */
function acc(node: BinaryTree, sum: number): number[] {
	sum += node.value;
	if (node.left === null && node.right === null) {
		return [sum];
	}
	return [
		...(node.left ? acc(node.left, sum) : []),
		...(node.right ? acc(node.right, sum) : []),
	];
}

/*
 * 보조함수를 호출하는 본 함수.
 */
export function branchSums(root: BinaryTree): number[] {
	return acc(root, 0);
}

엄청 단순한 코드인데 한참 고생해서 만들었다.

종료 조건

	if (node.left === null && node.right === null) {
		return [sum];
	}

처음에는 보조함수의 첫 파라메터가 노드와 함께 null도 받을 수 있게 만든 뒤, 노드 대신 null이면 종료 된 것으로 생각하고 지금까지 누산해 온 값을 반환하게 만들었는데, 리프 노드 왼쪽과 오른쪽에서 한 번씩 값이 반환되서 결과값이 두 번 씩 반복되어 버렸다.
그래서 파라미터에서 null 타입은 제외해버리고, 오른쪽과 왼쪽 노드가 전부 null인가 확인하는 방식으로 종료 조건을 만들었다.

재귀 호출

	sum += node.value;
    
    // 종료조건
	
    return [
		...(node.left ? acc(node.left, sum) : []),
		...(node.right ? acc(node.right, sum) : []),
	];

현재 노드의 값을 더해주는 연산은 종료 전에 해주지 않으면 리프 노드의 값이 더해지지 않은 채로 반환된다. 그렇다. 나는 정답을 두 번씩 반환하는 오답 다음에는 마지막 값을 더하지 않고 반환하는 오답을 냈다.

오른쪽 노드로 한 번, 왼쪽 노드로 한 번 씩 연산을 어떻게 분기하게 만들지 고민을 한 참 했다. return을 두 번 시킬 수도 없고...

저런 답이 어떻게 머릿속에서 나왔는지는 모르겠다. 어떻게 하나의 배열에 두 번을 넣을 생각을 했는지는 모르겠지만 넣고 나서 보니 컴파일러가 오류를 찾아줘서 전개 구문을 넣고, 삼항 연산자를 넣었다.

결론

뒷걸음질 치다가 쥐를 잡았다.

그래도 전부 우연히 풀린 것도 아니고, 고민해서 푼 부분 중에서 틀린 부분이 왜 틀렸었는지 나중에 비슷한 문제를 만났을 때 참고하기 위해서 기록으로 남겨둔다.