你好,我正在学习递归,目前我有几个技巧问题需要剖析-这里是递归函数之一
int rec(int niz[], int start, int end){
if (start == end)
{
return niz[start]; // vraca zadnji
}
int temp = rec(niz, start+1, end);
// control output
cout << "n-----n";
cout << "start " << start << endl;
cout << "niz[start] " << niz[start] << endl;
cout << "end " << end << endl;
cout << "temp " << temp << endl;
cout << "n-----------------------------------------n";
//contrl output end
return ((niz[start] < temp) ? niz[start] : temp);
}
我包括了一个cout块来控制通话中的锣。这是的主要部分
int niz[] = {1,2,3,4,5,6,7};
cout << rec(niz, 0, 3);
这是我的输出:
-----
start 2
niz[start] 3
end 3
temp 4
------------------
-----
start 1
niz[start] 2
end 3
temp 3
------------------
-----
start 0
niz[start] 1
end 3
temp 2
------------------
1
有人能解释一下temp值是如何计算和返回的吗?我是如何得到1作为这个函数的返回值的?
提前感谢!
int temp = rec(niz, start+1, end);
在这里,您可以在其中调用"rec"函数,但参数已更改(start+1(。您在彼此内部调用这些函数,直到"开始"等于"结束"(然后返回(
if (start == end)
{
return niz[start]; // vraca zadnji
}
在最深的一个返回后,第二深的继续流动,打印一些信息。
cout << "n-----n";
cout << "start " << start << endl;
cout << "niz[start] " << niz[start] << endl;
cout << "end " << end << endl;
cout << "temp " << temp << endl;
cout << "n-----------------------------------------n";
然后它返回niz[start]和temp(本地值(之间的最低值。
return ((niz[start] < temp) ? niz[start] : temp);
然后第三个最深的函数继续流动,以此类推。直到它到达第一个函数。
在您的主要部分中,您将end设置为3,因此它对前3个元素执行操作(它到达第四个元素,但除了返回其值之外,什么都不做(。通过比较作为开始传递的niz[0]和递归函数返回的temp(恰好相同(,可以得到1。它等于,所以返回值为niz[0],即1;
当使用递归函数时,您应该有某种"退出点"来防止递归变得无限,即
if (start == end)
{
return niz[start];
}
一般来说,递归函数如下所示:
f()
{
//return condition
//some work
f();
//some work
//return
}
你可以把它们看作这个
f()
{
//some code
f()
{
//some code
f()
{
//some code
f()
{
...
//eventually the return condition is met
}
//some code
//return
}
//some code
//return
}
//some code
//return
}
请注意,未处理的递归可能会导致内存泄漏,因为每个函数调用都会附带额外的数据。
f()
{
f();
}
由于已创建的系统数据,这将导致堆栈溢出;
你可能想看《盗梦空间》来更好地理解它:(
rec(niz, 0, 3) (D)
|
---->rec(niz, 1, 3) (C)
|
----> rec(niz, 2, 3) (B)
|
----> rec(niz, 3, 3) (A)
您调用(D(,它调用(C(来计算temp
,依此类推,直到(A(In(A(start==end
,返回niz[3]
=4
。
在(B(中:
temp = 4
((A(的结果(
start = 2
由于4
大于niz[start]
=3
(B(返回3
在(C(中:
temp = 3
((B(的结果(
start = 1
由于3
大于niz[start]
=2
(B(返回2
在(D(中:
temp = 2
((C(的结果(
start = 0
由于2
大于niz[start]
=1
(B(返回1
递归行位于打印语句块之前。根据递归的性质,它在递归行上调用函数,并停止调用方函数的执行,直到被调用方完成为止。因此,在打印当前元素之前,您需要处理下一个元素。
在您的示例中,会发生以下情况:
Layer 1:
Is start equal to end? No.
What is the result of the next element? Don't know yet, recurse.
Layer 2:
Is start equal to end? No.
What is the result of the next element? Don't know yet, recurse.
Layer 3:
Is start equal to end? No.
What is the result of the next element? Don't know yet, recurse.
Layer 4:
Is start equal to end? Yes!
Return the current element, 4.
End layer 4.
Layer 3:
Now know next element, start printing for the 3rd element.
Return 3.
End layer 3.
Layer 2:
Now know the next element, start printing for the 2nd element.
Return 2.
End layer 2.
Layer 1:
Now know the next element, start printing for the 1st element.
Return 1.
End layer 1.
End program.
正如您所看到的,数组元素是向后打印的,因为打印语句在递归调用之后。我希望它们按顺序打印,在递归调用之前打印,或者创建一个缓冲区并将每个打印部分附加到缓冲区的前面。