c - 需要递归函数的解决方案

Question

#include <stdio.h>

void call(int n )
{
    if ( n > 0 )
    {
        call(--n) ;
        printf("\n%d",n) ;
        call(--n) ;
    }
}

int main(void )
{
    int a = 3 ;
    call(a) ;
    return 0 ;
}

在上面提到的代码中，我很难理解其背后的逻辑。我得到 0 1 2 0 作为输出。为什么？

Answer 1

call(3)
│ n3=3
│ --n3 (n3=2)
├╴call(2)
│ │ n2=2
│ │ --n2 (n2=1)
│ ├╴call(1)
│ │ │ n1=1
│ │ │ --n1 (n1=0)
│ │ ├╴call(0)
│ │ │ └ return
│ │ │
│ │ │ printf("\n0");           ⇦ 0
│ │ │
│ │ │ --n1 (n1=-1)
│ │ ├╴call(-1)
│ │ │ └ return
│ │ └ return
│ │
│ │ printf("\n1")              ⇦ 1
│ │
│ │ --n2 (n2=0)
│ ├╴call(0)
│ │ └ return
│ └ return
│
│ printf("\n2");               ⇦ 2
│
│ --n3 (n3=1)
├╴call(1)
│ │ n1=1
│ │ --n1 (n2=0)
│ ├╴call(0)
│ │ └ return
│ │
│ │ printf("\n0");             ⇦ 0
│ │
│ │ --n1 (n1=-1)
│ ├╴call(-1)
│ │ └ return
│ └ return
└ return

Answer 2

首先，找到你的基本情况：call(n), when n<=0什么都不做，只是返回。

在一般情况下，code(n)定义说：“递减n并递归（一直向下）；当控件返回时，打印n（保留其值），再次递减并再次递归”。

或者，使用方程式：

call(n) | when(n<=0) = NO-OP
call(n) | otherwise  = call(n-1), print(n-1), call(n-2)

所以，

call(1) = call(0), print(0), call(-1)
        = print(0)

call(2) = call(1), print(1), call(0)
        = print(0), print(1)

call(3) = call(2), print(2), call(1)
        = (print(0), print(1)), print(2), print(0)

---

继续，

call(4) = 0120+3+01
call(5) = 0120301+4+0120
call(6) = 012030140120+5+0120301
....

似乎我们可以生成不确定的结果输出序列，只保留两个最近的值：

(n,a,b) --> (n+1,b,b+n+a)

因此，它不是向下递归到基本情况，而是描述远离起始情况的核心递归(2,0,1)（该1情况被一个特殊的事实所涵盖(1,_,0)）。我们可以将其编码为实际的无限增长（即“无限”）序列，或者我们可以从中创建一个无限循环。

这种非终止计算的目的是什么？为了描述结果的计算，一般来说。但是，当我们达到 的目标值时，当然很容易缩短这样的计算n。

好处？我们得到了一个迭代循环，而不是递归！

output(1) = "0"
output(n) | when(n>1) = 
   let {i = 2, a="0", b="1"}
   while( i<n ):
      i,a,b = (i+1),b,(b+"i"+a)
   return b

Answer 3

当试图理解代码流时，我无法避免我使用一个简单的策略：

以详细的方式记录输出。例如，您可以映射应用程序的流程，而不是在调用函数中使用简单的 printf 语句。这是一个例子

#include <stdio.h>

void call(int n, int depth)
{
    printf("%.*s(enter) n is (%d)\n", ++depth, "-----", n);
    if ( n > 0 )
    {
        call(--n, depth) ;

        call(--n, depth) ;
    }
    printf("%.*s(exit) n is (%d)\n", depth--, "-----", n);
}

int main(void )
{

    int a = 3 ;

    call(a, 0) ;
    getchar();
    return 0 ;
}

这将导致：

-(enter) n is (3)
--(enter) n is (2)
---(enter) n is (1)
----(enter) n is (0)
----(exit) n is (0)
----(enter) n is (-1)
----(exit) n is (-1)
---(exit) n is (-1)
---(enter) n is (0)
---(exit) n is (0)
--(exit) n is (0)
--(enter) n is (1)
---(enter) n is (0)
---(exit) n is (0)
---(enter) n is (-1)
---(exit) n is (-1)
--(exit) n is (-1)
-(exit) n is (1)