[Data Structures][02-1] 함수의 재귀적 호출의 이해

본 글은 윤성우의 열혈 자료구조 책을 읽고, 강의를 수강하고 복습한 것을 기록한 글입니다.

강의 교안 또한 참고하여 작성하였습니다.

(강의 교안의 경우 오렌지 미디어에서 다운로드할 수 있습니다)

---

목차
Chapter 02. 재 귀(Recursion)

Chapter 02-1: 함수의 재귀적 호출의 이해

- 재귀 함수의 기본적인 이해

- 재귀 함수의 디자인 사례

- 팩토리얼의 재귀적 구현

 

---

함수의 재귀적 호출의 이해

재귀 함수의 기본적인 이해

 

재귀 함수의 호출 원리는 컴퓨터 구조상에서 내가 만든 명령문, 즉 재귀 함수의 복사본이 계속 호출되는 것이다.

재진입이 아니라 계속 원본에서 복사본을 호출하는 것이다.

 

재귀 함수의 간단한 예

void Recursive(int num)
{
    if(num <= 0)	// 재귀의 탈출 조건
    	return;		// 재귀의 탈출!
    printf("Recursive call! %d \n", num);
    Recursive(num-1);
}

int main(void)
{
    Recursive(3);
    return 0;
}

 

실행결과

 

Recursive call! 3

Recursive call! 2

Recursive call! 1

 

---

재귀 함수의 디자인 사례

 

팩토리얼의 재귀적 특성

재귀 함수는 함수 내에서 함수를 호출하는 형식이므로 자료구조나 알고리즘의 어려운 문제를 단순화하는 데 사용되는 중요한 무기이다. 재귀 함수의 특성상 코드상으로 간단하게 옮길 수 있는 것이 특징이다. 위 예시처럼 탈출 조건을 작성하는 것을 의미한다.

 

---

팩토리얼의 재귀적 구현

 

팩토리얼 구현 결과

#include <stdio.h>

int Factorial(int n)
{
    if(n == 0)
    	return 1;
    else
    	return n * Factorial(n-1);
}

int main(void)
{
	printf("1! = %d \n", Factorial(1));
    printf("2! = %d \n", Factorial(2));
    printf("3! = %d \n", Factorial(3));
    printf("4! = %d \n", Factorial(4));
    printf("9! = %d \n", Factorial(9));
    return 0;
}

 

실행결과

 

1! = 1

2! = 2

3! = 6

4! = 24

9! = 362880

 

---

Reference

http://www.kyobobook.co.kr/product/detailViewKor.laf?ejkGb=KOR&mallGb=KOR&barcode=9788996094067&orderClick=LEa&Kc= 

윤성우의 열혈 자료구조 - 교보문고

 

http://www.orentec.co.kr/teachlist/teach_main.php

====== 오렌지 미디어 ======

 

---