4: 알고리즘-7(재귀:Recursion)

재귀: 프로그램이나 알고리즘의 스스로를 계속 호출하는 것, 함수 내부에서 자기 자신을 호출함

함수가 초기에 주어진 입력보다 더 작은 입력을 가지고 계속해서 자신을 호출함

반복문을 사용하는 코드는 항상 재귀함수를 통해 구현하는 것이 가능하고 그 반대도 가능함

---

피라미드 모양을 출력하기 위한 코드 작성하기

#

##

###

####

 

#include <cs50.h>
#include <stdio.h>
//draw 함수의 프로토타입
void draw(int h);

int main(void)
{   //사용자로부터 피라미드의 높이를 입력 받아 저장
    int height = get_int("Height: ");
    
    //draw 함수로 피라미드 그리기
    draw(height);
}
//draw 함수 구현하기(값을 반환할 필요없이 출력만 하기 때문에 void draw로 정의)
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>
//draw 함수의 프로토타입
void draw(int h);

int main(void)
{   //사용자로부터 피라미드의 높이를 입력 받아 저장
    int height = get_int("Height: ");
    
    //draw 함수로 피라미드 그리기
    draw(height);
}
//draw 함수 구현하기(값을 반환할 필요없이 출력만 하기 때문에 void draw로 정의)
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 만큼의 #을 출력함.
• 여기서 내부적으로 호출된 draw 함수를 따라가다 보면 h=0일 때 끝내야 함
• h=0일 때는 아무것도 출력을 하지 않도록 하는 조건문을 추가해 줘야 함(피라미드의 시작점)
• 이 조건문은 h-1 때문에 음수가 되더라도 계속 호출하지 않도록 막아주는 역할

---

재귀의 반복 개념:

1) 재귀의 호출은 같은 문제 내에서 더 범위가 작은 값, 즉, 하위 문제에 대해 이루어져야 함

2) 재귀함수 호출은 더 이상 반복되지 않는 base case에 도달해야 함(예, 러시아 인형)

 

https://gomguard.tistory.com/111

반드시 알아야하는 알고리즘 top 8 - 1. 재귀 알고리즘

https://www.boostcourse.org/cs112/joinLectures/41307

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