CS50 2019 (10)recursion, 쌓이는 것
===
모두를 위한 컴퓨터 과학 (CS50 2019)
부스트코스 무료 강의
www.boostcourse.org
1.컴퓨팅사고
2.C언어
3.배열
4.알고리즘
5.메모리
6.자료구조
=====================
7)재귀
최다득표자를 선거의 승자로 하거나 결선 투표로 하거나 여러명을 고르게 하거나 등의 알고리즘이 있다 생활에서도 다양하게 쓰이고 있다는 말
수많은 정렬 알고리즘이 존재한다 중요한 몇가지만 볼 것, O(n^2)보다 더 나은
이제부터 컴퓨터 공학을 배우면서 여러분의 생각을 흔들어 버릴 수많은 개념 중 하나를 소개할 것
목표는 경험해보는 것 다양한 개념을 적용하다보면 점차 익숙해질 것
===
재귀의 핵심 개념을 위해 예제를 하나 볼 것.
첫주에 했던 것, 그땐 반복문을 강조했었다.
이 알고리즘을 좀 다르게, 더 좋게 만들 수 있지 않을까? 물론 trade off가 있다
여기서 노란색의 반복문을 지워보고 생각해보자
남은것중에 Open to moddle of left(or right) ~ 의 이유는 남은 절반에서 찾기 위해서였음. 중요한 사실은 전화번호부의 크기를 절반으로 줄인다는 것. 알고리즘은 사실 똑같으니 의사코드를 저렇게 이것저것 다시하라고 하지 말고
저 화면의 코드는 Search라는 함수다.
재귀 함수는 내부에서 자기 자신을 호출합니다
뭔말인지 모를 수도 있지만 곧 자세히 배울 것임
저 함수 이름이 Search이고, Search left(right) half of book이라는 줄에서 Search함수를 반복적으로 호출하기 때문에 재귀
특정 줄로 가라고 할 필요 없이 무엇을 할지만 알려주기. 왼편 탐색해 오른편 탐색해라고 해보자.
순환논리처럼 보일 수도 있다. Mike Smith를 어떻게 찾아? Mike Smith를 찾아 하는것과 같은데
중요한 점은 단순히 같은 것을 반복시키는 게 아니라(반복문 말하는거겠지)
Mike Smith를 이렇게 큰 전화번호부에서 찾는 데 없다면 더 작은 크기에서 다시 찾아보라고 하며
알고리즘 다음 단계에서의 문제의 크기를 계속 절반으로 줄여나가는 겁니다. --이거를 설명하려고 저 내용으로 수업하심
이것이 재귀라는 프로그래밍 기법의 예시이다.
여러분의 프로그램이나 알고리듬이 스스로를 계속 호출하는 것
===
이걸 만드려면?
iteration.c --반복 이라는 뜻
*do-while은 제대로 입력하는지 확인할 때, 오늘은 안쓸게요 올바른 입력이 주어진다 가정하고
draw함수를 만들 것
값을 반환 안하고 출력만 하므로 void draw --구분하라고 직관에
입력으로 숫자 n을 받음 void draw(int h)
의사코드와 비슷하게 하기 위해 i를 1로 초기화하고(0부터 시작하는 것과 똑같지만 때로는 지금처럼 1부터 시작하는 것도 좋습니다)
i가 높이보다 작거나 같으면 계속하기 --1로 하면 작거나 '같다'를 해줘야 h만큼
만약 지금처럼 2차원에서 무언가를 하려 한다면 저처럼 중첩 반복문을 쓸 것입니다
h를 받으면
h번 반복할건데(세로)
반복마다 i가 1부터 증가하고, 그 i만큼 가로로 찍어내는 --▽보통 그 상황에서 변수들의 숫자가 뭐냐를 활용해야, 첫번째 줄일 째 한번 반복 두번째 줄일 때 두번 반복이니까 이걸 활용해야겠지
잘 된다!중첩 반복문으로 마리오 피라미드를 성공적으로 구현헀다
지금까지 본 문제들처럼 마리오 피라미드에는 흥미로운 점이 있어
이게 흔한 피라미드인가? 높이 4의 피라미드를 어떻게 정의하나? 분명 높이 3의 피라미드에 한 줄을 추가한것임
높이 3은 높이 2에서
높이2는 높이 1에서 한줄을 추가한 것
이것을 재귀적 정의라고 한다!!!
눈에 보이는 혹은 가상의 물체의 구조를 그 물체의 자체를 이용해서 설명하는 것을 말한다
특수한 경우 높이 1은 높이 0의 뭐야 아무것도 아니야
-> 반환, 종료 혹은 정지 등 알고리듬에 맞게 처리를 해야함
시작점에 대해서는 여러분들이 직접 이건 특별한 경우이므로 아무것도 하지 말고 재귀적으로 자기 자신을 호출하지 않도록 알려줘야 합니다
: ▽시작점은 특별하게 대해야 한다는 이런 것도 다 알려주네
===
recursion.c
이번엔 중첩 반복문을 사용하지 않고 작은 피라미드로 큰 피라미드를 정의해볼 것
(프로토타입 이따가 마지막에 적음)
4짜리 그리려면 제일 먼저 뭘 해야 할까? 3짜리를 그리면 된다, 어떻게 코드로 적나??
그리고 이러면 무한 반복호출되고 있어 3, 2, 1, 0, -1, -2.. 처럼 빼기만 하면 안끝나
어떤 조건에서 그리지 말아야 할지(=시작점)의 조건을 줘야 한다
하드 코딩된 조건문으로 의도치 않은 반복을 막는 것
그리고
높이4의 피라미드를 그릴 땐
(1)높이 3의 피라미드를 그리고
(2)한 줄 추가한다
draw(h-1)가 피라미드를 그려주는 애라고 생각하면
이제 여기에 한 줄을 추가로 그려주는 부분을 구현해야 한다
h가 4 일 때 4개의 #을 그리는 반복문
반복문이 필요하지만, 한 번이면 충분합니다
(이번 강의에서 이런거 엄청 많이 알려주네 이렇게 하는거 맞아? 응 맞아 식의 중의중에 정해주는 설명)
여기까지의 코드가 놀랍게도 다야.
명시적으로 출력한건 한줄에 해당하는 벽돌뿐인데!!
▽
draw(h-1)이 draw(h-2)랑 한줄 출력으로 변한다
draw가 전부 바뀌면
h=0일때 return되고
h=1일때의 출력
h=2일때의 출력
h=3일때의 출력
h=4일때의 출력
이 됨
(내 생각)머릿속에 프랙탈이 되고 있는 코드 내용을 상상하자 그 안에서 계속 코드가 있는 것임 인자만 -1되면서
재귀적으로 스스로를 호출하면서
이진 탐색이나 분할 정복법에서처럼
기존 문제보다 더 작은 크기의 문제를 풀어갑니다
3개가 필요한거군
시작점 조건
재귀함수
한줄추가
문제를 조금씩 먹어가는것
몇 주 후 스택을 배우면서 이 마법이 어떻게 가능한지 볼 것임
우선은 함수가 초기에 주어진 입력보다 더 작은 입력을 갖고 계속해서 자신을 호출한다는 것만 이해합시다
===
네이버 :
재귀
함수를 사용할 때 어디에서 호출했나요? main 안에서 프로그램을 작성하면서 필요한 순간에 호출하여 사용합니다.
그런데 main 역시 함수라는걸 기억하시나요? main이라는 함수 안에서 또 다른 함수를 사용한 것입니다.
이 사실을 알게 되었을 때, 우리는 함수가 본인 스스로를 호출해서 사용할 수 있는지에 대해 의문을 가질 수 있습니다.
이에 대한 대답은 할 수 있다 이며, 이러한 것을 재귀(Recursion)라고 부릅니다.
아래와 같이 피라미드 모양을 출력하기 위해 다음과 같은 코드를 작성할 수 있습니다
#
##
###
####
#include <cs50.h>
#include <stdio.h>
void draw(int h);
int main(void)
{
// 사용자로부터 피라미드의 높이를 입력 받아 저장
int height = get_int("Height: ");
// 피라미드 그리기
draw(height);
}
void draw(int h)
{
// 높이가 h인 피라미드 그리기
for (int i = 1; i <= h; i++)
{
for (int j = 1; j <= i; j++)
{
printf("#");
}
printf("\n");
}
}높이를 입력 받아 중첩 루프를 통해 피라미드를 출력해주는 draw 함수를 정의한 것이죠.
여기서 꼭 중첩 루프를 써야만 할까요? 사실 바깥 쪽 루프는 안 쪽 루프에서 수행하는 내용을 반복하도록 하는 것일 뿐입니다.
따라서 바깥 쪽 루프를 없앤 draw함수를 만들고, 이를 ‘재귀적으로’ 호출하도록 해서 똑같은 작업을 수행할 수 있습니다.
즉, draw 함수 안에서 draw 함수를 호출 하는 것이죠. 아래 코드와 같이 수정할 수 있습니다.
#include <cs50.h>
#include <stdio.h>
void draw(int h);
int main(void)
{
int height = get_int("Height: ");
draw(height);
}
void draw(int h)
{
// 높이가 0이라면 (그릴 필요가 없다면)
if (h == 0)
{
return;
}
// 높이가 h-1인 피라미드 그리기
draw(h - 1);
// 피라미드에서 폭이 h인 한 층 그리기
for (int i = 0; i < h; i++)
{
printf("#");
}
printf("\n");
}draw 함수 안에서 draw 함수를 다시 호출 하는 부분을 유의하시기 바랍니다.
h라는 높이를 받았을 때, h-1 높이로 draw 함수를 먼저 호출하고, 그 후에 h 만큼의 #을 출력합니다.(▽재귀를 할 때마다 함수의 인자가 바뀌고 h의 조건이 바뀐다) 여기서 내부적으로 호출된 draw 함수를 따라가다 보면 h = 0인 상황이 오게 됩니다. 따라서 그 때는 아무것도 출력을 하지 않도록 하는 조건문을 추가해줘야 합니다.
이렇게 재귀를 사용하면 중첩 루프를 사용하지 않고도 하나의 함수로 동일한 작업을 수행할 수 있습니다.
---
내 직관
재귀는 이 문제에서 볼 수 있듯이 뒤에 쌓아놓을 수가 있다
쌓아놓는다는게 뭐냐면
재귀가
h=5
1
재귀(h-1)
2
면
5-1, 4-1, 3-1, 2-1, 1-1 1-2, 2-2, 3-2, 4-2, 5-2 이런식으로 동작하겠네?
h=1
1
재귀(h+1)
2
면
1-1, 2-1, 3-1, 4-1, 5-1, 5-2, 4-2, 3-2, 2-2, 1-2 이렇고
재귀함수 앞뒤 코드로 나눠서
앞에것만 일단 h조건 다르게 실행하고
뒤에것을 거꾸로 h조건 다르게 실행가능