这题固然可以用斐波那契数列来写,但是普适性还是不太好,作为新手我也是一开始看不懂递归,有了chatgpt辅助才明白什么意思,特此写此题解。
先上y总源代码
#include <iostream>
using namespace std;
int n;
int ans;
void f(int k)
{
if (k == n) ans ++ ;
else if (k < n)
{
f(k + 1);
f(k + 2);
}
}
int main()
{
cin >> n;
f(0);
cout << ans << endl;
return 0;
}
看看chatgpt的解释:
Each recursive call to the function f
creates a new instance of the function with its own set of local variables, including k
. These instances of the function are essentially independent and exist simultaneously in the call stack.
So, when f(0)
is called, it leads to subsequent calls like f(1)
, f(2)
, and so on, until eventually, f(5)
is called. At this point, f(5)
checks if k
is equal to n
(assuming n
is 5), and if so, it increments ans
. However, this incrementation only affects the ans
variable in the instance of the function f(5)
.
After f(5)
finishes executing (whether ans
was incremented or not), program control returns to the previous instance of the function, which would be f(4)
. The same process repeats until all instances of the function have finished executing or terminated due to k
exceeding n
.
So, in essence, each call to f
leads to a chain of subsequent calls until the base case is reached or until k
exceeds n
. After each call to f
finishes, program control returns to the previous call in the call stack until all calls have been resolved.
也就是说,一开始k=0.这个k=0放到f函数中会唤起f(1) 和 f(2),依次类推,到f(5)的时候结束并且ans ++执行。这样的话f(0)像一颗树一样分叉,最后的根部末端是八个f(5),也就是执行f(0)的话根据它的规则,最后会执行八次f(5),然后停止。这样的话ans就等于8了
不知道我理解的对不对,欢迎批评指正
关于这个k的问题,可以理解为一个k唤起很多进程,这些进程中的变量虽然叫k但是和原先的k不一样。这个k在等于5之后进程结束后就不再被使用,接下来进行子函数f中别的进程,而不是“这个”k变成4之后再去执行递归。
感谢xiuzhiyuan同学的一些解答和帮助
So when the recursive search tree method is used. Is the one variable used throughtout the whole process or one variable asked the process and they ask the function to branch and execute the function like a tree root?
In a recursive search tree method, typically, the state or configuration of the search process is represented by multiple variables. These variables may change as the search progresses from one node to another in the search tree.
Consider the example of depth-first search (DFS), which is often implemented using recursion and a recursive search tree. In DFS, the state of the search process is typically represented by multiple variables, including the current node being explored, the current path followed, and possibly other auxiliary variables related to the problem being solved.
When a function is called recursively in the context of a recursive search tree, it’s like traversing from one node to another in the tree. Each recursive call corresponds to exploring a potential successor state or configuration. The variables passed to each recursive call may change to reflect the transition from one node to another in the search tree.
To summarize, in a recursive search tree method:
- Multiple variables may be used to represent the state or configuration of the search process.
- Each recursive call corresponds to exploring a potential successor state or configuration in the search tree.
- The variables passed to each recursive call may change to reflect the transition from one node to another in the search tree.
“by multiply variables” 指出了关键
附上我与chatgpt的一些问答