정확히 말하면, 머릿속에 함수 실행 순서를 그리려고 하지 말라는 것이다. 이유는 머릿속에서 재귀에 재귀에 재귀에 재귀를 따라가보면 어는 순간 핀트가 나가버리기 때문이다.
그래서 중요한 것은 재귀 함수의 중요한 부분에 초첨을 맞춰 문제를 풀어나가는 것이다.
재귀가 풀리는 4단계 접근법
1.
재귀를 꼭 써야 하는가?
반복 대신 재귀를 써야하는 경우인지 생각해본다.
재귀함수를 사용해서 푸는 문제의 대부분은 반복을 사용해서도 풀수 있다.
복잡한 문제를 더 작은 문제로 쪼개고, 작은 문제를 반복적으로 풀고, 작은 답들을 조합해서 전체 문제를 해결한다.
그리고 일반적으로 성능은 반복문이 재귀함수보다 더 좋다.
그렇기에 꼭 재귀함수를 써야하는지 먼저 체크해본다.
2.
베이스 조건
답을 바로 알 수 있는 가장 간단한 상황을 생각한다.
재귀함수는 무한루프에 빠질 경우가 많다. 그렇기에 베이스 조건을 가장 먼저 만들어야 한다. 베이스 조건에서 무엇을 return 해야할지 헷갈린다면 문제에서 요구한 답의 데이터 타입을 본다.
예시로 주어진 인풋 값을 보고, 답으로 만드는 방법을 생각하면 함수 실행 순서를 떠올린다. 그보다 문제에 초점을 맞춰 베이스 조건을 만들어보자.
3.
분해
베이스 조건에 가까워지도록 인풋값을 조작한다.
예를 들어, n이라는 정수로 함수를 실행한다면, 자기 자신을 호출할때는 n-1을 넣는다. 그래야 재귀함수가 반복하면서 인풋값이 조금식 더 간단해진다.
재귀적 분해라고도 하는데 인풋값을 간단하게 만들어서 문제를 더 작게 만드는 것이다. 이 재귀적 분해에는 패턴이 보이기도 한다.
정수 : 수를 줄여나간다. n-1 or n-2
배열 : 앞의 숫자를 없애 길이를 줄인다. [1, 2, 3, 4] → [2, 3, 4] → [3, 4]
링크드 리스트 : 포인터가 가리키는 다음 노드가 input으로 들어간다.
트리 : 자식 노드를 하나씩 넣는다. (이진 트리의 경우 재귀 호출을 2번 하는 경우가 많다.)
4.
조합
부분 답을 가지고 전체 답을 구하는 방법을 생각해본다.
재귀 함수가 베이스 조건에서 멈추고 return된 값을 조합해 전체 문제를 해결한다. 여기서 중요한 것은 전체 과정을 머리속에 그리지 않는 것이다.
왜냐하면, 위에서 계속 말했듯 최대한 재귀적으로 생각하지 않는게 목표이기 때문이다. 그럼 조합은 어떻게 할까? 대개 두 가지 케이스로 풀린다.
a.
베이스 조건 바로 위 단계
b.
베이스 조건 3단계 위
Recursive leap of faith
재귀 함수가 제대로 동작한다고 믿고, 그 믿음을 바탕으로 함수의 나머지 부분을 구성하는 접근 방식이다. 위에서 말한 두가지 케이스가 올바르게 나온다면 나머지도 잘 나올거라 믿음 하나로 설계하는 것이다.
그렇다. 재귀함수는 믿음. 그 뿐이다.
Subscribe to 'kyugntae-ai'
Welcome to 'kyugntae-ai'!
By subscribing to my site, you'll be the first to receive notifications and emails about the latest updates, including new posts.
Join SlashPage and subscribe to 'kyugntae-ai'!
클라이언트와 서버 클라이언트 요청을 보내는 사용자 서버 클라우드 서버 웹 서버 데이터베이스 서버 어플리케이션 서버 프록시 서버 데이터베이스 테이블 표 열 행 DBMS (데이터베이스 관리 시스템) RDBMS(관계형 데이터베이스 관리 시스템) MySQL PosgreSQL SQLite
서경태
TIL 웹개발 - 소프트웨어 설계
자료 자료구조 데이터를 효과적으로 젖아하기 위해 어떤 논리나 규칙으로 자료를 모안호은 구조 선형 구조 자료간의 관계가 1:1로 순차적으로 나열되어 있는 것 배열 : 메모리상에 연속적인 공간에 데이터를 저장하는 방법 리스트 : 메모리상에 임이의 위치에 데이터를 저장하지만 각 데이터들이 앞뒤 관계를 갖게 하는 방법 스택 : 선입후출 방식의 자료구조. 히스토리 기능을 구현할 때 유용하고 DFS(깊이우선탐색), 후위연산, 백트래킹, 유효성 검사 등 다양한 곳에 사용된다. 큐 : 선입선출 방식의 자료구조. 작업스케쥴링 기능을 구현하거나 BFS(너비우선탐색), 티켓 시스템 등 다양한 곳에서 사용된다. 비션형 구조 자료들 간 관계가 1:N으로 나열되어 있는 것을 의미한다. 그래프: 노드와 간선으로 이루어진 자료구조 무방향 그래프 / 방향 그래프 / 가중치 그래프 트리: 그래프의 한 종류로 싸이클의 구조가 없어야 한다. 이진트리 : 각 부모노드의 자식 노드가 최대 2개인 트리 편향트리 : 한쪽으로만 자식을 갖는 트리 포화이진트리 : 이진트리에서 모든 부모가 2개의 자식노드를 갖는 이진트리 완전이진트리 : 이진트리에서 거의 모든 노드가 채워져 있으며 강한한 제일 왼쪽부터 채워져 있는 이진트리 프로그래밍 기본
서경태
TIL 웹개발 - CS 기초 지식
메인보드 컴퓨터 본체 내부에 위치한, 주회로가 내장된 보드이다. CPU (Central Processing Unit) 컴퓨터의 두뇌 역할을 하는 실질적으로 모든 기능을 수행하는 요소 입력을 받은 명령을 해석/연산 한 후에 결과값을 출력장치로 전달하는 컴퓨터의 주요 부품 GPU (Graphic Processing Unit) 병렬 연산에 특화되어 이전에는 3D 그래픽을 처리하는데 많이 사용했지만 현재는 범용적으로 사용된다. 주기억장치 (RAM) 휘발성 메모리로 컴퓨터를 껏다 키면 메모리가 사라진다. DRAM SRAM 보조기억장치 비휘발성 메모리로 컴퓨터를 껐카 켜도 메모리가 사라지지 않는다. HDD : 물리적인 보조기억장치 SSD : 반도체에 전기 신호를 이용하여 데이터를 적재하는 보조기억장치 OS 운영체제란 사용자가 컴퓨터를 조작 및 제어하고 작업의 편의성을 제공하기 위한 '시스템 소프트웨어'입니다.
