难以理解连续的递归调用

Question

我试图理解以下程序，其中存在连续的递归函数调用，但在跟踪大头钉的加载方式时感到困惑。

void func(char*);  // function prototype

int main(){
    func("123");
    return 0;
}

void func(char a[]){
    if(a[1]=='[=10=]')
        return;
    func(a+1);
    func(a+1);
    printf("%c",a[1]);
}

这个输出是 3 3 2

如果有人能就此提出建议，我们将不胜感激...

这种多次递归调用是否有任何好处或在特定问题领域找到应用程序..？

Answer 1

只需将自己置于 CPU 的位置并逐行执行（或使用调试器来帮助完成该任务）。

第一个电话是

func("123")

本次调用不满足终止条件a[1] == '[=14=]'，故调用

func("23");

对 func("23") 的调用依次调用

func("3")

确实满足 return 条件。因此，调用 returns 给前一个调用者 func("23").

func("23") 继续调用 func("3") 由于行

func(a+1);
func(a+1);

继续这个在你脑海中执行程序的过程，并写下每次调用 printf 的内容。这将解释您的输出。

更新

请注意，对 printf() 的调用发生在递归调用之后，例如致电

func("123")

会像

一样进行

输入 func("123")
不满足终止条件
调用 func("23")
再次调用 func("23")
Printf("3")（这是一个[1]）
Return

Answer 2

posted 代码是一个设计相当糟糕的递归实例。

以下代码具有正确的 'tail' 递归形式。

将反转后的字符串传回 main 并让 main 打印出来会更好。

它颠倒了 main() 传递给 func() 的字符串的顺序

请在询问运行时问题时，post 编写编译代码，包括必要的头文件#includes，这样我们就不会猜测要包含哪些头文件

#include <stdio.h>

void func(char*);  // function prototype

int main(){
    func("123");
    return 0;
}

void func(char a[])
{
    if(a[1]=='[=10=]')   // check for end of recursive sequence
    {
        printf( "%c", a[0] ); // last tail action
        return;
    }

    func(a+1);    // step+next recursion
    printf( "%c", a[0] ); // tail action
    return;
}

Answer 3

递归可以简单理解如下

例如：

Func(int a){
    while(a>1)
        return a * func(a-1);
}

假设a = 5.

发生的事情是 returns 5 * func(4).

现在func(4)returns4 * func(3)然后就这样继续下去

查看 this example for use of recursion in fibonacci series。

Answer 4

使用断点调试是理解递归的一种方式。另一种方法是绘制递归调用树。

从图中可以看出，在level0之后的每一层中，由于这两行代码，每两个节点之后都会出现printf语句：

func(a+1);
func(a+1);

一般来说，对于任何长度大于 0 的输入字符串，这将成为一个完美的二叉树。节点总数由以下公式给出：

2^(k+1) - 1 // k is the depth; here k = 2

执行的printf语句总数可以通过这个公式得到：

2^k - 1 // For k=2, there will be 3 printf statements each printing 3,3,2 respectively

难以理解连续的递归调用

difficulty in understanding successive recursive calls

c

recursion

stack