Ruby에서 재귀란 무엇입니까?
재귀 함수는 최종 목표에 도달할 때까지 계속 자신을 호출하는 함수입니다(기본 사례라고도 함). ). 각 함수 호출 후 이 기본 사례로 진행하여 남은 작업량을 줄입니다.
기본 사례에 도달하면 재귀가 종료되고 함수가 반환되기 시작합니다.
루비 재귀
재귀에 대해 배우기 시작하는 고전적인 예는 계승 수를 계산하는 것입니다.
반복과 재귀를 모두 사용하여 Ruby에서 이 작업을 수행하는 방법을 봅시다!
숫자의 계승을 계산하려면 1부터 목표 숫자까지 모든 숫자를 곱해야 합니다. 예를 들어 5의 계승은 다음과 같습니다. 1 * 2 * 3 * 4 * 5 = 120 .
Ruby와 재귀를 사용하여 이 작업을 수행하는 방법을 살펴보겠습니다.
예 :
def iterative_factorial(n) (1..n).inject(:*)enddef recursive_factorial(n) # 기본 케이스 return 1 if n <=1 # 재귀 호출 n * recursive_factorial(n-1)end
이 예에서는 계승 수를 계산하는 두 가지 방법을 보여줍니다. 반복 및 재귀 솔루션.
재귀 솔루션에서 우리는 작업 중인 숫자(n-1)를 줄임으로써 진행합니다. 한 번(n <=1) 더 이상 재귀 호출이 없으며 다음과 같은 일이 발생합니다.
return 1 # recursive_factorial(1)return 2 * 1 # recursive_factorial(2)return 3 * 2 # recursive_factorial(3)return 4 * 6 # recursive_factorial(4)return 5 * 24 # recursive_factorial(5)
Ruby 개발자로서 우리는 대부분의 경우 반복적인 솔루션을 사용합니다. 그것도 훌륭하지만 재귀가 어떻게 작동하는지 아는 것은 여전히 가치가 있다고 생각합니다.
이제 또 다른 고전적인 예인 피보나치 수를 살펴보겠습니다.
피보나치 수열
Leonardo Fibonacci는 이상적인 조건에서 토끼 개체군의 성장을 모델링하는 방법을 조사할 때 이 수열을 발견했습니다.
순서는 현재 숫자 앞에 오는 두 숫자를 더하여 계산됩니다.
예 :
1, 1, 2, 3, 5, 8, 13, 21
Ruby에서 이를 계산하려면 재귀 함수를 사용할 수 있습니다.
def fib(n) n <2인 경우 n을 반환 fib(n-1) + fib(n-2)end
이 함수와 범위를 사용하면 처음 20개의 피보나치 수를 쉽게 계산할 수 있습니다.
(1..20).각 { |n| fib(n) } 하지만 문제가 있습니다 :
귀하의 기능은 필요하지 않은 많은 추가 작업을 수행하고 있습니다. 이를 설명하기 위해 다음 이미지를 보십시오.
이미지에서 fib(3) 다섯 번 계산됩니다. 더 긴 피보나치 수열을 계산하려고 하면 함수가 정말 느려집니다.
해결책? 메모이제이션.
메모이제이션:이미 수행한 작업 재사용
이전 단계에서 이미 수행한 작업을 다시 사용할 수 있다면 좋지 않을까요?
메모이제이션을 사용하여 이를 수행할 수 있습니다. .
값비싼 계산 결과를 저장하기 위해 캐시를 사용합니다. 이 경우 배열이 수행됩니다.
예 :
@cache =[0,1]def fib(n) @cache[n] if @cache[n] @cache[n] =fib(n-1) + fib(n-2)end먼저 결과가 이미 캐시에 있는지 확인하고, 캐시에 있으면 반환하고, 그렇지 않으면 계산을 수행하고 결과를 저장합니다.
이것은 훨씬 더 빠르게 실행되고 훨씬 더 큰 피보나치 수를 계산할 수 있습니다.
재귀의 한계
독자가 친절하게 지적했듯이 재귀 솔루션은
SystemStackError: stack level too deep로 실패할 수 있습니다. 큰 입력 숫자(약 7500, 정확한 숫자는 시스템에 따라 다름).더 큰 수를 계산해야 하는 경우 반복 솔루션을 사용해야 합니다.
예 :
메모 =[](0..n).각각 |i| 메모[i] =i <2 ? i :메모[i-1] + 메모[i-2]끝결론
재귀는 훌륭하지만 때로는 이해하기 어려울 수 있습니다. 이제 당신의 차례입니다. 연습이 숙달됩니다!
이 게시물이 마음에 든다면 공유하고 내 뉴스레터를 구독하세요 🙂