[알고리즘] 재귀

학습 목표

함수를 재귀적으로 사용하는 코드를 작성할 수 있다.

1. 재귀?

• main에서 필요할 때 다른 함수들을 호출해서 사용했던 상황을 떠올려 보자. 생각해보면 main도 함수인데 main이라는 함수 안에서 다른 함수를 호출해서 사용한 것이다.
• 그렇다면 함수가 본인 스스로를 호출해서 사용할 수 있을까?
  -> YES. 이를 재귀(Recursion)라고 부른다.
  
  

2. 피라미드를 출력하자

#

##

###

####

#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 만큼의 #을 출력한다.
  여기서 내부적으로 호출된 draw 함수를 따라가다 보면 h = 0인 상황이 오게 되는데 이때는 아무것도 출력을 하지 않도록 하는 조건문을 추가해줘야 한다.
• 피라미드 4층 짜리는 사실 피라미드 3층 + 1층 추가 해준 것이라는 설명을 떠올리며 기억하자.