피보나치 재귀 함수는 어떻게 "작동"합니까?
저는 Javascript를 처음 접했고 함수 재귀를 설명하는 장에 왔을 때 그것을 읽고있었습니다. 피보나치 수열의 n 번째 숫자를 찾기 위해 예제 함수를 사용했습니다. 코드는 다음과 같습니다.
function fibonacci(n) {
if (n < 2){
return 1;
}else{
return fibonacci(n-2) + fibonacci(n-1);
}
}
console.log(fibonacci(7));
//Returns 21
이 기능이 무엇을하는지 정확히 파악하는 데 문제가 있습니다. 누군가 여기서 무슨 일이 일어나고 있는지 설명 할 수 있습니까? 함수가 자신을 호출하는 5 번째 줄에 갇혀 있습니다. 여기서 무슨 일이 일어나고 있습니까?
당신은 그 자체로 함수를 정의하고 있습니다. 일반적으로 fibonnaci(n) = fibonnaci(n - 2) + fibonnaci(n - 1). 우리는이 관계를 코드로 표현하고 있습니다. 따라서 fibonnaci(7)다음을 관찰 할 수 있습니다.
fibonacci(7)fibonacci(6)+와 같다fibonacci(5)fibonacci(6)fibonacci(5)+와 같다fibonacci(4)fibonacci(5)fibonacci(4)+와 같다fibonacci(3)fibonacci(4)fibonacci(3)+와 같다fibonacci(2)fibonacci(3)fibonacci(2)+와 같다fibonacci(1)fibonacci(2)fibonacci(1)+와 같다fibonacci(0)fibonacci(1)1과 같다fibonacci(0)1과 같다
이제 fibonacci(7)원래 목표였던 을 평가 하는 데 필요한 모든 부분 이 준비되었습니다. 것을 알 기본 케이스 - -이 가능하게하는 것이다. 이것이 재귀를 막는 것이므로 스택을 풀고 각 단계에서 반환하는 값을 합산하는 프로세스를 시작할 수 있습니다. 이 단계가 없으면 프로그램이 마침내 충돌 할 때까지 더 작고 더 작은 값을 계속 호출 합니다.return 1n < 2fibonacci
이를 설명하는 몇 가지 로깅 문을 추가하면 도움이 될 수 있습니다.
function fibonacci(n, c) {
var indent = "";
for (var i = 0; i < c; i++) {
indent += " ";
}
console.log(indent + "fibonacci(" + n + ")");
if (n < 2) {
return 1;
} else {
return fibonacci(n - 2, c + 4) + fibonacci(n - 1, c + 4);
}
}
console.log(fibonacci(7, 0));
산출:
fibonacci(7)
fibonacci(5)
fibonacci(3)
fibonacci(1)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(4)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(3)
fibonacci(1)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(6)
fibonacci(4)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(3)
fibonacci(1)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(5)
fibonacci(3)
fibonacci(1)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(4)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(3)
fibonacci(1)
fibonacci(2)
fibonacci(0)
fibonacci(1)
동일한 수준의 들여 쓰기에있는 값이 합산되어 이전 수준의 들여 쓰기에 대한 결과가 생성됩니다.
여기에는 좋은 답이 많이 있지만 함수의 결과를 더 잘 설명하는 데 도움이되는이 다이어그램을 만들었습니다. 반환 될 유일한 값은 1 또는 0입니다 (이 예에서는 n <2에 대해 1을 반환하지만 대신 n을 반환해야합니다).
이는 각 재귀 호출이 결국 0 또는 1을 반환하게됨을 의미합니다. 이들은 결국 스택에 "캐시"되고 원래 호출로 "이동"되어 함께 추가됩니다.
따라서 'n'의 각 값에 대해 동일한 다이어그램을 그리면 수동으로 답을 찾을 수 있습니다.
이 다이어그램은 fib (5)에 대해 모든 함수가 반환되는 방식을 대략적으로 보여줍니다.
이것은 제어 흐름, 즉 함수의 실행 순서를 보여줍니다. 코드는 항상 왼쪽-> 오른쪽 및 위쪽-> 아래쪽으로 실행됩니다. 따라서 새 함수가 호출 될 때마다 일시 중지되고 다음 호출이 발생합니다.
다음은 원본 게시물을 기반으로 한 실제 제어 흐름을 보여줍니다. 기본 조건은 if (n <= 0) {return 0} else if (n <= 2) {return 1;}단순화를위한 것입니다.
1. fib(5) {
return fib(4) + fib(3);
2. fib(4) {
return fib(3) + fib(2);
3. fib(3) {
return fib(2) + fib(1);
4. fib(2) {
A= return 1;
};
5. fib(1) {
B= return 1;
};
C= return 2; // (1 + 1)
};
6. fib(2) {
D= return 1;
};
E= return 3; // (2 + 1)
};
7. fib(3) {
return fib(2) + fib(1);
8. fib(2) {
F= return 1;
};
9. fib(1) {
G= return 1;
};
H= return 2; // (1 + 1)
};
I= return 5; // (3 + 2)
};
1 단계) fibonacci(7)호출 될 때 다음을 상상해보십시오 (모든 n을 7로 변경 한 방법에 주목하십시오).
function fibonacci(7) {
if (7 < 2){
return 1;
}else{
return fibonacci(7-2) + fibonacci(7-1);
}
}
단계 2) (7 < 2)명백히 거짓 이므로 , 우리 는 처음 fibonacci(7-2) + fibonacci(7-1);으로 fibonacci(5) + fibonacci(6);이후로 변환되는 것으로 이동하여 fibonacci(5)호출됩니다 (이번에는 n을 5로 변경).
function fibonacci(5) {
if (5 < 2){
return 1;
}else{
return fibonacci(5-2) + fibonacci(5-1);
}
}
3 단계) 그리고 또는 코스 fibonacci(6)도 호출되므로 모든 사람이 fibonacci2 개의 새로운 호출을 fibonacci호출합니다.
심상:
fibonacci(7)
____|_____
| |
fibonacci(5) fibonacci(6)
____|____ ____|_____
| | | |
fib(3) fib(4) fib(4) fib(5)
어떻게 분기되는지 보십니까? 언제 멈출까요? n2 미만이 되면 if (n < 2). 이 시점에서 분기가 중지되고 모든 것이 합쳐집니다.
다음이 도움이되기를 바랍니다. 부름:
fibonacci(3)
라인 5에 도착하여 다음을 수행합니다.
return fibonacci(1) + fibonacci(2);
첫 번째 표현식은 함수를 다시 호출하고 1 (이후 n < 2)을 반환합니다 .
두 번째는 함수를 다시 호출하고 5 번째 줄에 도달하여 다음을 수행합니다.
return fibonacci(0) + fibonacci(1);
두 표현식 모두 1을 반환하므로 ( n < 2둘 다에 대해)이 함수 호출은 2를 반환합니다.
그래서 답은 1 + 2, 즉 3입니다.
이 두 함수가 재귀에 대한 훨씬 더 명확한 설명을 제공했다고 생각합니다 (이 블로그 게시물에서 ).
function fibDriver(n) {
return n === 0 ? 0 : fib(0, 1, n);
}
function fib(a, b, n) {
return n === 1 ? b : fib(b, a + b, n-1);
}
n 번째 피보나치 수를 계산하려면 관계식은 F (n) = F (n-2) + F (n-1)입니다.
If we implement the relation in the code, for nth number, we calculate the (n-2)th and (n-1)th number using the same method.
Each subsequent number is the sum of the previous two numbers. Thus, the seventh number is the sum of the sixth and fifth numbers. More generally, the nth number is the sum of n - 2 and n - 1, as long as n > 2. As recursive functions need a stop condition to stop recursing, here n<2 is the condition.
f(7) = F(6) + F(5);
in turn, F(6) = F(5) + F(4)
F(5) = F(4) + F(3)... it goes on until n<2
F(1) returns 1
/*
* Steps Fibonacci recursion
* 1) 3 gets passed. (3 is printed to the screen during this call)
* 2) Fibonacci A gets decrements by 2 and recursion happens passing 1 as a param. (1 is printed to the screen during this call)
* 3) Fibonacci A hits the base case returning 1 and it "unwinds". (No recursion here)
* 4) Fibonacci B gets called, decrementing the previous value of n (3 was the previous value of n before A made the returning call) to 2. (2 is printed to the screen during this call)
* 5) Fibonacci A is called again subtracting 2 from n (2-2=0) and passes 0 as a param. (1 is printed to the screen during this call since it's converted from 0)
* 6) Fibonacci A hits the base case and "unwinds" (no recursion here)
* 7) Fibonacci B is called subtracting 1 from 2 (2 was the previous value of n before A made the returning call) and passes 1 as a param. (1 is printed to the screen during this call)
* 7) Fibonacci B now hits the base case, returning 1 and "unwinds" (no recursion here)
* 8) Fibonacci B retraces it's steps back through All previous fucntion calls and values of n (n=2 in our case) and adds [them] to the copy of n=1 stored in its local scope
* 9) Once Fibonacci B completes the "unwinding" process, it returns the calculated value to the original caller (no recursion here)
Note*
Each instance of Fibonacci recursion creates its own scope and stores the returned value in a copy of n (in our case 1).
As it the function "unwinds" it executes subsequent code that receive the value of n at that time. (all functions that call other functions "unwind" back through previous calls once they return)
In the last call of our Fibonacci example, Fibonacci B receives the value of n=2 as Fibonaccci A "unwinds" since that was the last value before it made the returning call.
Once Fibonacci B reached the base case and "unwound", it retraced its steps back through all previous values of n (in our case just n=2) and added [them] to its local copy of n=1.
* The result when passing the number 3 is:
3
1
2
1
1
(3)
*/
var div = document.getElementById('fib');
function fib( n, c ) {
var indent = "";
for (var i = 0; i < c; i++) {
indent += " ";
}
var v = n===0 ? 1 : n
var el = document.createElement('div'),
text = indent + "fibonacci(" + v + ")";
el.innerHTML = text;
div.appendChild(el);
if(n<2){
return 1;
}
return fib(n-2, c + 4) + fib(n-1, c + 4);
}
The function is calling itself. That's simply the definition of a recursive function. In the 5th line it is transferring execution to itself by passing parameters that will result in a value.
To ensure that a recursive function doesn't turn into an endless loop, there must be some sort of condition that doesn't call itself. The goal of your code in the question is to perform the calculations of a fibonacci sequence.
Fibonacci algorithm with recursive function based on ES6
const fibonacci = ( n, k = 1, fib2 = 0, fib1 = 1 ) => {
return k === n ?
(() => { return fib1; })()
:
(() => {
k++;
return fibonacci(n, k, fib1, fib1 + fib2);
})();
}
console.info(' fibonacci ' + 11 + ' = ' + fibonacci(11));
look, fib is
t(n) = t(n - 1) + n;
if n = 0 then 1
so let see how recursion works, I just replace n in t(n) with n-1 and so on. it looks:
t(n-1) = t(n - 2) + n+1;
t(n-1) = t(n - 3) + n+1 + n;
t(n-1) = t(n - 4) + n+1 + n+2 + n;
.
.
.
t(n) = t(n-k)+ ... + (n-k-3) + (n-k-2)+ (n-k-1)+ n ;
we know if t(0)=(n-k) equals to 1 then n-k=0 so n=k we replace k with n:
t(n) = t(n-n)+ ... + (n-n+3) + (n-n+2)+ (n-n+1)+ n ;
if we omit n-n then:
t(n)= t(0)+ ... + 3+2+1+(n-1)+n;
so 3+2+1+(n-1)+n is natural number. it calculates as Σ3+2+1+(n-1)+n = n(n+1)/2 => n²+n/2
the result for fib is : O(1 + n²) = O(n²)
This the best way to understand recursive relation
Sharing a simpler code for fib in JS/ES6 using recursion.
function fib(n, first = 1, second = 1) {
if (n <= 2) return 1;
[first, second] = [second, first + second];
return (n - 2 === 1) ? second : fib(n - 1, first, second);
}
console.log(fib(10));
참고 URL : https://stackoverflow.com/questions/8845154/how-does-the-fibonacci-recursive-function-work
'Programing' 카테고리의 다른 글
| 자바 스크립트 배열에서 요소를 제거하는 깨끗한 방법 (jQuery, coffeescript 사용) (0) | 2020.12.07 |
|---|---|
| CPU가 SSE3 명령 세트를 지원하는지 확인하는 방법은 무엇입니까? (0) | 2020.12.07 |
| class << Ruby를 사용한 self vs self.method : 무엇이 더 낫습니까? (0) | 2020.12.07 |
| Meteor를 중지하는 방법? (0) | 2020.12.07 |
| Long 대신 Integer를 사용하는 이유는 무엇입니까? (0) | 2020.12.07 |