[알고리즘_기초]3. 재귀함수(Python,Java)

인터넷의 어느 짤의 일부분을 가져왔습니다.

"""

어느 한 컴퓨터공학과  학생이 유명한 교수님을 찾아가 물었다.

"재귀함수가 뭔가요?"

"잘 들어보게. 옛날에 산 꼭대기에 현자가 있었어. 질문엔 모두 지혜롭게 대답해 주었지.

그런데 어느날, 그 선인에게 한 선비가 찾아와서 물었어.

"재귀함수가 뭔가요?"

"잘들어보게. 옛날에 산 꼭대기..

"""

 

재귀함수가 뭐냐는 질문에 똑같은 대답을 반복하는 교수님 ㅋㅋ

재귀 함수는 어떤 함수 안에서 자기 자신을 부르는 것을 말합니다 .

 

아래의 파이썬 코드를 예시를 들겠습니다.

def recursion():
    print("recursion..")
    recursion()

recursion()

"recursion" 을 출력하고 또 다시 자기 자신을 호출하여 "recursion"을 출력합니다 . 그리고 또 자신을 호출하여.... 

계속 반복을 합니다.  빠져 나갈  조건이 없기때문에 좋지 않은 함수입니다.

재귀 함수는 꼭 종료 조건이 필요합니다.

 

팩토리얼을 구하는 함수로 재귀함수를 구현해보겠습니다.

팩토리얼은 아래와 같습니다.

10! = 10 * 9 * 8 * ..... * 3 * 2 * 1 

5! = 5 * 4 * 3 * 2 *1

코드로 구현 해보면 

def factorial_fun(n):
    result = 1
    for i in range(1,n+1):
        result *= i
    return result

print(factorial_fun(5))
print(factorial_fun(10))

1 부터 n 까지 총 합을 구하는 함수와 매우 비슷하죠.

 

그럼 재귀함수를 사용하여 구하기전에 분석을 해보면

5! =  5 * 4! 과 같습니다

4! = 4 * 3! 과 같습니다

3! = 3 * 2! 과 같습니다

2! = 2 * 1 과 같습니다 

그러면  2!부터 위로 정리를 하면

2! 은 2 * 1   이므로  3! = 3 * (2 * 1) 이 됩니다.

4! 은 4 * 3! 이므로 4! = 4 * (3* (2*1) )이 됩니다.

5!은 5 * 4! 이므로 5! = 5 * (4 * (3* (2*1) ) )이 됩니다.

5!은 4!을 부르고 4!은 3!을 부르면서 n-1 씩 증가하다 1이 되었을때 멈춥니다.

 

 

<recursion.py>

def fact(n):
    if n <= 1:
        return 1
    return n * fact(n-1)

print(fact(5))

 

<recursion.java>

public class recursion {
    public static void main(String[] args){
        int result = fact(5);

        System.out.println(result);
    }

    private static int fact(int i) {
        if (i <= 1){
            return 1;
        }
        return i * fact(i-1);
    }
}