재귀 알고리즘 [계승계산]

재귀 알고리즘 [계산 팩토리얼]

2024-07-12

재귀 알고리즘함수를 허용하는 컴퓨터 과학 및 수학에서 널리 사용되는 프로그래밍 기술입니다.직접또는간접적인땅스스로를 부르다 문제를 해결하기 위해.재귀적기본 아이디어복잡한 문제를 더 작고 유사한 하위 문제로 분해하여 이러한 하위 문제가 직접 해결될 수 있을 만큼 간단해질 때까지 분해하는 것입니다.

재귀 알고리즘은 일반적으로 두 가지 주요 부분으로 구성됩니다.

기본 사례: 재귀 호출의 종료 조건입니다. 즉, 추가 재귀 호출 없이 직접 응답할 수 있는 가장 간단한 문제 인스턴스입니다.
재귀 사례: 문제를 더 작은 하위 문제로 나누고 재귀 호출을 통해 이러한 하위 문제를 해결하는 프로세스입니다. 재귀 사례는 각 호출이 기본 사례를 향해 진행되고 있는지 확인해야 합니다.

재귀 알고리즘의 단계:

기본 사례 식별: 추가 재귀 호출 없이 직접 해결할 수 있는 문제를 결정합니다.
재귀 상황 설계: 큰 문제를 더 작은 하위 문제로 나누는 방법과 솔루션을 하위 문제에 결합하여 원래 문제에 대한 솔루션을 얻는 방법을 정의합니다.
재귀 수렴 보장: 재귀 호출이 결국 기본 사례에 도달하고 무한 재귀를 방지하도록 보장합니다.

재귀 알고리즘의 장점과 단점:

이점: 코드가 간결하고 논리가 명확하며 이해하고 작성하기 쉽습니다.
결점 : 더 많은 함수 호출 오버헤드가 포함되므로 반복 솔루션보다 효율성이 떨어질 수 있습니다. 또한 너무 깊은 재귀로 인해 스택 오버플로 오류가 발생할 수 있습니다.

재귀는 다음과 같은 많은 알고리즘에 적용됩니다.트리 순회、그래프 검색、동적 프로그래밍 등 . 재귀를 적절하게 사용하면 복잡한 문제 해결을 단순화할 수 있습니다.

예: 계승 계산

def factorial(n):#自定义求n的阶乘函数
        if n==1:#判断n=1
                return 1#返回1结束
        else:#递归条件 即n!=1
                return n*factorial(n-1)#递归求阶乘

number = int(input("请输入一个正整数:"))#输入n的值
result = factorial(number)#调用阶乘函数
print("%d 的阶乘是 %d" %(number,result))#输出结果
1
2
3
4
5
6
7
8
9

여기에 이미지 설명을 삽입하세요.

코드 설명

factorial 함수는 매개변수를 받습니다. n 는 계승을 계산할 수를 나타냅니다.계승은 다음과 같이 표현됩니다.n!, 이하 모두로 정의됨 n 양의 정수의 곱입니다. 예를 들어,5! = 5 × 4 × 3 × 2 × 1 = 120。

함수 내부:

기본 사례: if n 1과 같으면 함수는 1을 직접 반환합니다. 1의 계승값이 1로 정의되므로 이것이 재귀의 종료 조건입니다.
재귀 사례: if n 가 1과 같지 않으면 함수는 다음과 같습니다.n 그리고factorial(n-1) 결과가 곱해집니다.factorial(n-1) 사실이다factorial 기능통화 자체 , 그러나 매개변수는 1만큼 감소합니다.이 통화는 다음까지 계속됩니다.n 1에 도달합니다.

재귀의 핵심은 각 재귀 호출이 기본 사례에 더 가깝게 이동하여 결국 기본 사례에 도달하고 값을 반환하기 시작한다는 것입니다. 이 예에서 각 재귀 호출은 n이 1이 될 때까지 n을 1씩 감소시킵니다.

알아채다:

재귀에서는 각 함수 호출이 스택 공간의 일부를 차지하기 때문에 큰 값을 처리할 때 성능 문제나 스택 오버플로 오류가 발생할 수 있습니다. 계승과 같은 간단한 수학 연산의 경우 더 효율적이고 메모리 친화적인 반복 방법이 있는 경우가 많습니다. 그러나 재귀는 특정 문제를 해결하는 우아하고 이해하기 쉬운 방법을 제공합니다.

기술나눔