小菜想问这代码是什么，看不懂，递归算法那里？

Question

#include<stdio.h>
void f(int *a,int i,int max);
int main()
{
    int n;
    int a[100];
    scanf("%d",&n);
    f(a,0,n);
    return 0;
}
void f(int *a,int i,int max)
{
    if(i==max)
    {
         int j;
         printf("<");
         for(j=0;j<max;j++)
         if(a[j])
             printf("true,");
         else 
             printf("false,");
         printf("\b>\n");
    }
    else
    {
        a[i]=0;
        f(a,i+1,max);
        a[i]=1;
        f(a,i+1,max);
    }
}

比如输入数字4，于是max=4，而i=0，于是if语句就跳到else上面，所以a[0]=0；继续执行递归f（a,1,4）;然而依然不满足if的条件，所以继续执行递归，等等。。。。我就晕了，，，不知道它怎么得出结论的。可能有些知识上我给忘了，希望有人能帮我理清下逻辑关系，谢谢啦！

Answer 1

这是输出 n 位二进制的所有情况吧。

递归就是不停将原有的问题划分为若干相同的子问题。

else
{
    a[i]=0;
    f(a,i+1,max);
    a[i]=1;
    f(a,i+1,max);
}

这里就是把当前位划分为两种情况，0 和 1 。

比如下面，考虑第一位取 0 的时候，将剩余的位置又当做整体让 f 来处理。

  ↓  
0 口口口口口口口口口口口口口

if() 里就是指当箭头到达最右边的时候，把当前的情况输出来。

比如第一种情况，到达最右之后就输出 n 个 false 。

                            ↓  
0 0 0 0 0 0 0 0 0 0 0 0 0 0 _

然后最后一次的 f 开始“归”，倒数第二个 f 开始考虑 1 的情况。

                          ↓  
0 0 0 0 0 0 0 0 0 0 0 0 0 1 

然后在调用一次 f ，又到了最右，再次输出这个数组

                            ↓  
0 0 0 0 0 0 0 0 0 0 0 0 0 1 _

这次最后一个 f “归”后，倒数第二个 f 也要“归”了，到了倒数第三个 f。

                        ↓  
0 0 0 0 0 0 0 0 0 0 0 0 1 口 

以此类推计算下去。

当第一位为 0 的所有情况输出完之后，再 f 又回到第一位，开始考虑 1 的情况。

  ↓  
1 口口口口口口口口口口口口口

同上，计算下去。

大概就是个这么情况，这种指数级时间复杂度的算法没有什么实际意义，当了解递归就好。

【完】

Answer 2

每次递归i都在+1，所以第四次递归的时候if就成立了，这个时候最里层的递归结束，仔细想下，或者断点跑下这个程序

Answer 3

第一次i=0,但是这句话

f(a,i+1,max);

将i+1作为本函数的i,所以i=1,如此递归下去,直到i==max,不就结束递归了吗