CS50 2019 (10)recursion, 쌓이는 것

===

www.boostcourse.org/cs112

모두를 위한 컴퓨터 과학 (CS50 2019)

1.컴퓨팅사고

2.C언어

3.배열

4.알고리즘

5.메모리

6.자료구조

 

=====================

7)재귀

h가 3, 2, 1일때 draw(2), draw(1), draw(0)으로 실행된다. draw(0)이 실행되고 바로 return될 뿐

최다득표자를 선거의 승자로 하거나 결선 투표로 하거나 여러명을 고르게 하거나 등의 알고리즘이 있다 생활에서도 다양하게 쓰이고 있다는 말

 

수많은 정렬 알고리즘이 존재한다 중요한 몇가지만 볼 것, 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조건 다르게 실행가능