需要一个关于递归函数的解决方案

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)

因此,而不是递归下来,对基本情况,介绍corecursion了从开始的情况下离开,(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