재귀

재귀함수란?

    재귀함수 : 함수 내에서 자기 자신을 다시 호출하는 함수를 의미

 

사용 가능한 재귀 함수

    1. 재귀의 탈출이 조건을 통해 가능함.

    2. 매개변수를 바꿔서 호출.

    *재귀 함수를 잘못 사용하면 무한루프에서 빠져나오지 못할 수도 있기 때문에 주의!

 

예) 피보나치 수열 : Fibonacci Sequence

                   0                                            n=1

fibo(n)={     1                                            n=2

                   Fibo(n-1)+Fibo(n-2)              otherwise

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

예) 이진 탐색 알고리즘의 재귀적 구현

    1. 탐색 범위의 중앙에 목표 값이 저장되었는지 확인

    2. 저장되지 않았다면 탐색 범위를 반으로 줄여서 다시 탐색 시작

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

출처 : 윤성의 열혈 자료구조