[기초] 재귀함수

재귀함수

자기 자신을 다시 호출하는 형태의 함수

C언어는 재귀적인 함수호출을 허용한다.

Recursive

재귀함수는 언제 이용?

Process를 이해(Process의 구성과 실행)하고 있는 것이 프로그래밍할때 아주 도움됨

컴퓨터구조/OS 이해(컴퓨터구조 먼저 듣고 다음 OS)

 

stack overflow: 재귀적 함수호출이 끝나지 않고 계속 이어져 메모리 부족으로 이어지는 문제

무한 재귀 호출을 피하기 위해 탈출 조건이 필요함!

적절한 탈출 조건을 만들어 주는것이 중요하다.

 

재귀 함수를 공부하는 이유

자료구조(데이터를 표현하는 방식)나 알고리즘(데이터를 효율적으로 해결하는 방법)을 공부할 때 재귀함수의 유용성을 알 수 있음

 

재귀 함수 Design 사례

1. 팩토리얼(factorial) 계산을 위한 알고리즘

ex.)

5! = 5 x 4x 3 x 2 x 1

0! = 1

 

n! = nx(n-1)x(n-2)x(n-3).....x2x1

n! = nx(n-1)!

 

f(n) = n x f(n-1) // n<=1

f(n) = 1 // n=0