[python]팩토리얼과 재귀함수

def facto(n):
        f = 1
        for i in range(1, n+1):
            f *= i
        return f
    
    print(facto(10))

팩토리얼은 1부터 n까지 연속한 숫자를 차례로 곱한 값. '계승'이라고도 불림

1! = 1
3! = 1*2*3 = 6
...
n! = 1*2*3*...*(n-1)*n

터미널에서 실행하게되면 3628800 의 값을 출력하게 된다.

재귀적 용법으로 구현하기

---

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

역시 위와 마찬가지로 3628800 의 값을 출력하게 된다.

주의할 점으로 재귀적 용법을 사용할 때는 반드시 종료 조건을 추가해서 재귀 에러나 스택 오버플로우가 나지 않도록 조심할 것.

계산 복잡도

---

첫번째 방법의 코드는 곱셈이 n번 필요하기 때문에 빅오 표기법으로 계산 복잡도는 O(n)이다.

재귀적 용법을 통한 코드는 4를 구할때 곱셈이 3번, 3을 구할때 곱셈이 2번.

즉 곱셈이 n-1번 필요하지만 빅오 표기법으로는 결국 똑같은 O(n)이다.

계산 복잡도도 똑같은데 왜 재귀함수를 쓰는거지?

---

사실 재귀 함수를 사용함으로써 성능적인 이득을 보려는 경우는 거의 없다. 다만 소스를 간략화 할 수 있어서 한 눈에 볼 수 있는 가독성을 제공한다.

하지만 가독성이라는 것도 기준에 따라 다른 거라서, 재귀적 용법에 대한 이해가 없다면 이마저도 쓸모가 없다. 재귀용법을 이해하지 못하는데 아무리 코드가 짧고 한눈에 볼 수 있다는게 무슨 장점인가.

그래서 쓰는 이유를 정리하면 다음과 같다.

1. 알고리즘 시험 공부에 나온다(...)
2. 변수 사용을 줄여준다.

1번 내용은...넘어가고 2번은 단순이 위에 올려둔 두개의 코드만 비교하더라도 재귀적 용법을 사용하면 n이라는 매게 변수만 필요한 것에 비해 첫번째 코드블럭은 매게 변수, 반환 값, 반복문에 사용하는 변수들이 필요하다.

1부터 n가지의 합 구하기를 재귀 호출로 만들기

---

def n_sum(n):
        if n <=1:
            return 1
        return n+n_sum(n-1)
    print(n_sum(3))

생각보다 간단하다. 종료조건으로 1보다 같거나 작을 경우 1을 리턴해주고 n-1씩 계속 줄여주면서 더해주면 된다.

숫자 n개 중에서 최댓값 찾기를 재귀 호출로 만들기

---

def max_num(num, n):
        if n == 1: #배열에 한개밖에 값이 안들어있을 경우
           return num[0]
        temp = max_num(num, n-1) #맨 끝에 배열부터 앞쪽으로 옮기면서 temp에 대입해주는 재귀호출
        if temp > num[n-1]:#검색해서 찾은 것보다 이전에 찾은게 더 크면 이전에껄 리턴
            return temp
        else:
            return num[n-1]#검색해서 찾은 것이 더 크거나 같으면 검색해서 찾은 걸 리턴
    num = [20,2,50,53,21,33,84,36,62,10]
    n = len(num)
    print(max_num(num, n))