재귀
재귀는 문제를 나누고 해결하는 데 유용합니다. 각 재귀 호출 자체는 다른 재귀 호출을 분리합니다. 재귀 함수의 중심에는 두 가지 유형의 케이스가 있습니다. 재귀를 종료할 시기를 알려주는 기본 케이스와 해당 함수를 호출하는 재귀 케이스입니다. 재귀 솔루션을 자연스럽게 사용하는 간단한 문제는 계승 계산입니다. 재귀 계승 알고리즘에는 n =0일 때 기본 케이스와 n>0일 때 재귀 케이스의 두 가지 경우가 있습니다.
역추적
역추적은 일부 계산 문제에 대한 솔루션을 찾기 위한 일반적인 알고리즘으로, 솔루션에 대한 선택 사항을 점진적으로 구축하고 불가능한 솔루션으로 이어지는 트랙의 지속적인 처리를 거부합니다. 역추적을 사용하면 이전 선택이 실수로 판명될 경우 취소할 수 있습니다.
팩토리얼의 일반적인 구현은 다음과 같습니다. -
예시
def factorial(n): #test for a base case if n==0: return 1 # make a calculation and a recursive call f= n*factorial(n-1) print(f) return(f) factorial(4)
이 코드는 숫자 1, 2, 4, 24를 출력합니다. 계승 4를 계산하려면 4개의 재귀 호출과 초기 상위 호출이 필요합니다.