1. c언어 재귀함수

[ dev c++ 다운로드 ]

https://sourceforge.net/projects/orwelldevcpp/

 

재귀 함수

 

▶ 정의 – Recursion(리커전, 되부름법)이란 ‘ 단위 프로그램에서 자신을 호출하여 문제를 해결하는 알고리즘 기법을 말한다. 즉 함수에서 자기 자신을 다시 호출하는 것을 말한다.’

이 기법은

          - 생각을 명료하게하고,

          - 표현을 단순하게 할 수 있지만,

          - 처리 시간이 길어지고, 자원 소모가 많은 특징이 있습니다.

시간 지연과 자원 소모가 맣은 치명적 단점에도 불구하고 장점이 워낙 커서 가장 중요한 알고리즘 기법으로 인식되고 있다.

 

이러한 Recursion은 2개의 중요한 부분이 있고, 두 번째 부분에는 3개의 구성요소가 있습니다.

           - 종료 처리부 : 바로 처리할 수 있는 간단한 프로그램

           - 되부름 처리부

            ①분할(divide) : 문제를 더 단순하거나 더 작게 하는 부분

            ②호출(call) : 자신을 호출하는 부분

            ③결합(combine) : 부분의 해결을 전체로 결합하는 부분

 

다음의 C코드를 보자.

c언어 재귀함수

  main 함수에서 함수 fun을 호출해 제어가 넘어간다. 그런데 함수 fun에서 다시 함수 fun을 호출하는 과정이 반복되는데, 이와 같이 자신을 호출하는 것을 ‘재귀호출’이라고 한다. 그런데 위와 같은 프로그램은 실행이 종료되지 않고 무한 반복 실행되므로 재귀호출 함수는 재귀호출이 종료되는 조건은 반드시 설정해 주어야 한다.

  재귀 호출이 이루어질 때마다 문제는 점점 작아져야 하며, 또한 재귀 호출이 끝이 나는 조건이 있어야 한다는 것이다.

 

[ c언어 재귀함수 1부터 n까지 함 ]

c언어 재귀함수

 

[ c언어 재귀함수 팩토리얼 ]

  팩토리얼이란 주어진 양의 정수에 대해 1부터 그 숫자까지의 모든 정수를 곱하여 나온 수로 n!로 표기한다.

  5!은 다음과 같다.

  Fact(5) = 5 * fact(4)

            = 5 * 4 * fact(3);

            = 5 * 4 * 3 * fact(2);

            = 5 * 4 * 3 * 2 * fact(1);

            = 5 * 4 * 3 * 2 * 1

c언어 재귀함수 팩토리얼

[  c언어 재귀함수 피보나치수열 ]

피보나치 수열은 다음과 같다.

      1 1 2 3 5 8 13 21 …………

  피보나치 수열은 처음 두항의 값은 1이지만,나머지 수열에서 n항은 n-1항과 n-2항을 더한 값이다. 피보나치 수열의 n항을 fibo(n)이라 하면 다음과 같다.

Fibo(n) = fibo(n-1) + fibo(n-2)  단, fibo(1) = fibo(2) = 1

입력받은 n번째 항을 출력하는 프로그램을 작성하시오.

c언어 재귀함수 피보나치수열