[CS50 4주차] Recursion

• 함수는 특정한 시점에 필요한 계산 값을 또 다른 자기 자신을 사용해서 구할 수 있음. 
• 재귀호출(recursive call)은 함수 f(x)가 값을 구하기 위해 자기 자신 f(x)을 호출하는 표현이 포함된 상황.
  • 함수가 본인 스스로를 호출해서 사용할 수 있음.
  • 반복문으로 구현한 코드보다 재귀호출로 구현한 코드가 좀 더 직관적.
  • 무한루프에 빠진 경우
    • 함수 호출을 메모리의 스택을 사용함.
    • 계속 자기 함수를 호출하다가 스택이 넘치게 됨. >> stack overflow에러 발생

• 단순하게 자기 자신을 다시 호출하게 되면 무한루프에 빠질 수 있음. 다음 경우와같이 변화를 주어 무한루프에 빠지지않도록 해야함.
  • 자기 자신f(x)를 다시 호출하는 경우
  •  단순하게 결과값만 반환하는 경우 
  • 함수의 반복 횟수를 계산하기 위해 매개변수 count를 지정하는 경우 

#include <stdio.h>

void hello(int count)
{
    if (count == 0)    // 종료 조건을 만듦. count가 0이면 다시 hello 함수를 호출하지 않고 끝냄
        return;

    printf("Hello, world! %d\n", count);

    hello(--count);    // count를 감소시켜서 다시 hello에 넣음
}

int main()
{
    hello(5);    // hello 함수 호출

    return 0;
}

dojang.io/mod/page/view.php?id=584

C 언어 코딩 도장: 67.1 재귀호출 사용하기

재귀를 사용하여 팩토리얼 함수 구하기

$n! = 1\times2\times3\times...\times(n-1)\times n$

$n! = (n-1)!\times n$

$fact(n) = fact(n-1)!\\times n$

n=1라면 1! = 1을 반환
n >=2 fact(n - 1)! * n을 반환

#include <stdio.h>

int factorial(int n)
{
    if (n == 1)      // n이 1일 때
        return 1;    // 1을 반환하고 재귀호출을 끝냄

    return n * factorial(n - 1);    // n과 factorial 함수에 n - 1을 넣어서 반환된 값을 곱함
}

int main()
{
    printf("%d", factorial(5));

    return 0;
}

 

재귀 factorial이 스택메모리에 할당되고 종료되는 과정

 

#include <cs50.h>
#include <stdio.h>
void draw(int h);

int main(void)
{
    int height = get_int("Height: ");
    draw(height);
}

void draw(int h)
{
    if (h == 0)
    {
        return;
    }

    draw(h-1);

    for(int i = 0; i < h; i++)
    {
        printf("#");
    }
    printf("\n");
}