recursion함수- (1~n까지의 합/ factorial 함수 구현하기)

 

chap.2 순환 (recursion)

 

recursion의 정의 :자기가 자기를 부르는 것 (재귀 호출) function 호출과 다른 개념

 

1. 1부터 n까지의 합을 구해 반환하는 함수

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

/*
   1-n까지의 합을 구해 반환하는 함수
*/

int sumToN(int n) {
   int sum = 0; // 합 결과를 저장하는 변수
   int i;
   for (i = 1; i <= n; i++) {
      sum += i;
   }
   return sum;
}

int main() {
   
   int result;
   result = sumToN(10); // 1부터 10까지의 합
   printf("1부터 10까지의 합은: %d\n", result);
   return 0;
}

 

💡

생각해보자!

10까지의 합이란?

내가 만약 1~9까지의 합을 알고 있다면, 거기에 10만 더하면 된다.

 

이 상상력을 바탕으로 코드를 수정해보면,

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>


int sumToN_recursion(int n) {

   //return 10+sumToN_recursion(9);
   return n + sumToN_recursion(n-1);
}

int main() { //c언어에는 main함수가 필수! -main에서 다른 함수를 호출하면서 코드가 시작됨
   
   int result;
   result = sumToN_recursion(10); // 1부터 10까지의 합
   printf("1부터 10까지의 합은: %d\n", result);
   return 0;
}

근데 이 코드에도 문제점이 존재한다. 우리가 구해야하는 값은 1부터 10까지의 합인데, 이 코드를 실행시켜보면 10에서 - 무한대까지 계속 더해나가게 된다.

 

 

상단에 있는 코드의 문제점은 탈출조건이 없다는 것이다.

 

 

💡

recursion함수는 탈출조건, 상상을 끝내는조건, 즉 자기자신을 더이상 호출하지 않는 조건이 반드시 필요하다.

 

탈출조건을 포함하여 코드를 작성하면 다음과 같다.

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h>  int sumToN_recursion(int n) {        if (n == 0) {       return 0;//s(0)은 0으로 반환 -->3+2+1+0로 바뀜    }    return n + sumToN_recursion(n-1); }  int main() { //c언어에는 main함수가 필수! -main에서 다른 함수를 호출하면서 코드가 시작됨        int result;    result = sumToN_recursion(10); // 1부터 10까지의 합    printf("1부터 10까지의 합은: %d\n", result);    return 0; }

상단의 작동과정을 좀 더 자세하게 풀어보자.

 

※작동과정 (10까지 모두 살펴보기 어려우니 3으로 바꿔 생각보겠다./ s는 sumToN_recursion 함수의 줄임)

 

 

s(3)의 return값은 3+s(2)

s(2) 의 return값은 2+s(1)

s(1)의 return값은 1+s(0)

 

s(0)는 전달인자가 0이므로 탈출조건이다.

s(0)의 return값은 0이다.

 

3+s(2)=3+(2+s(1))=3+2+(1+s(0))=3+2+1+0=6

 

---

 

이번엔 factorial함수를 살펴보자.

💡

factorial함수 구하기 ex) 3!= 3*2*1 이 함수는 n!를 계산하는 함수

 

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h>  int fact_recursion(int n) {        if (n == 1) {       return 1;    }    return n *fact_recursion(n-1); }  int main() {        int result;    int n;    scanf("%d", &n);    result = fact_recursion(n); // 1부터 10까지의 합    printf("1부터 n까지의 곱은: %d\n", result);    return 0; }

작동과정을 자세하게 풀어서 살펴보자.

 

※작동과정 (10까지 모두 살펴보기 어려우니 3으로 바꿔 생각보겠다./ c는 fact_recursion 함수의 줄임)

 

c(3)의 return값은 3*c(2)이다.

3*c(2)의 return값은 3*2*c(1)이다.

 

c(1)는 전달인자가 1이므로 탈출조건이다.

3*2*c(1)의 return값은 3*2*1이다.

 

---

 

recursion함수의 장단점

💡

recursion의 장단점은 되게 중요하다. 잘 알고 있자. (책 p.51쪽에 자세히 나와있다.)

 

1) 장점: 알고리즘 구현이 직관적이고 매우 쉽다.

 

2) 단점: 수행시간이 오래 걸리고, 메모리 소모가 많아 잘못하면 프로그램이 죽을 수 있다.

 

---

 

이번엔 recursion을 이용하여 거듭제곱을 구해보자.

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h>  int s(int n) {    //탈출조건    if (n == 0) {       return 1;    }     //상상력        return 2 *s(n-1); }  int main() {         int result;    int n;    scanf("%d", &n);    result = s(n); // 2의 n승 구하기    printf("2^n은: %d\n", result);    return 0; }

작동과정을 자세하게 풀어서 살펴보자.

 

※작동과정 (10까지 모두 살펴보기 어려우니 3으로 바꿔 생각보겠다.)

 

s(3)의 return값은 2*s(2)이다.

2*s(2)의 return값은 2*2*s(1)이다.

2*2*s(1)의 return값은 2*2*2*s(0)이다.

 

s(0)는 전달인자가 0이므로 탈출조건이다.

2*2*2*s(0)의 return값은 2*2*2*1이다.

 

---

위에서 구한 2의 거듭제곱 코드를 조금 더 바꿔보자.

여기서 사용되는 개념은

$2^4=(2^2{)}^2$이다.

 

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h>  int s(int m, int n) {    //탈출조건    if (n == 0) {       return 1;    }     if (n%2 == 0) { //n은 차수       return s(m*m,n/2);    }    else {       return m * (s(m * m ,(n - 1) / 2)); //2^9=2*2^8=2*(2^2)^4//==2*(2^2^2)^2    }  }  int main() {        int result;    int m,n;    scanf("%d %d",&m, &n);    result = s(m,n); // m의 n승 구하기    printf("m의 n승은: %d\n", result);    return 0; }

예시를 보며 코드를 더 자세하게 이해해 보자.

 

1) m이 3이고, n이 7인 경우

 

n%2 ≠ 0 이므로 return값은 m * (s(m * m ,(n - 1) / 2));

 

왜 이런 결과가 나오는 걸까? 잘 생각해보자

💡

지수가 홀수인 경우$3^6=(3^2{)}^3$처럼 묶을 수 없다.

그렇기 때문에 지수를 짝수로 만들어주기 위해서$3^7=3\ast 3^6$을 이용하는 것이다.

작동과정을 자세하게 살펴보자.

 

s(3,7)의 return값은 n%2 ≠ 0이므로 3*s(3*3,3)이다. —3*(3^2)*(9^2)

s($3^2$,3)의 return값은 n%2 ≠ 0이므로$3^2$*s($9^2$,1)이다. —3^2*(9^2)*1

s($9^2$,1)의 return값은 n%2 ≠ 0이므로$9^2$*s($81^2$,0)이다. - 9^2*1

s($81^2$,0)의 return값은 n=0이므로 1이다.

⇒ 3*3*3*3*3*3*3

 

2)m이 5이고, n이 8인 경우

 

n%2 = 0 이므로 return값은 s(m * m , n / 2))

 

작동과정을 자세하게 살펴보자.

 

s(5,8)의 return값은 n%2 = 0이므로 s(5*5,4)이다.

s($5^2$,4)의 return값은 n%2 = 0이므로 s($25^2$,2)이다.

s($25^2$,2)의 return값은 n%2 = 0이므로 s($625^2$,1)이다.

s($625^2$,1)의 return값은 n%2 ≠ 0이므로$625^2$*s($625^4$,0)이다.

s($625^4$,0)의 return값은 n=0이므로 1이다.

⇒$625^2\ast 1$$=25^4=5^8$

 

---

 

이번엔 recursion함수를 이용하여 피보나치 수열 함수를 만들어 보자.

 

피보나치 수열이란?

💡

피보나치 수열은 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다.

편의상 0번째항을 0으로 두기도 한다.

 

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h>  /*   피보나치 수열   n번째 피보나치 수열의 숫자는? */  int fibo(int n) {    //탈출조건    if (n == 0) {       return 0;    }     if (n == 1) {       return 1;    }    //상상력        return fibo(n - 1) + fibo(n - 2); }  int main() {        int result;    int n;    scanf("%d", &n);    result = fibo(n); // 피보나치 수열의 n번째숫자    printf("피보나치 수열의 n번째 항은: %d\n", result);    return 0; }

천천히 작동과정을 살펴보자.

 

피보나치 수열의 형태는 다음과 같다. (0번째 수: 0 ,1번째 수: 1)

* 0,1,1,2,3,5,8

 

n이 5라고 가정하고 작동과정을 살펴보면,

f(5)의 return값은

f(4)+f(3)

이다. f(4)+f(3)의 return값은

(f(3)+f(2))

+

(f(2)+f(1))

이다. (f(3)+f(2))+(f(2)+f(1))의 return값은

(f(2)+f(1))

+

(f(1)+f(0))

+

(f(1)+f(0))

+

f(1)

이다.

(f(2)+f(1))+(f(1)+f(0))+(f(1)+f(0))+f(1)의 return값은

(f(1)+f(0))+f(1)+(f(1)+f(0))+(f(1)+f(0))+f(1)

1+0+1+1+0+1+0+1 =5

 

---

 

 

 

Uploaded by Notion2Tistory v1.0.0