Simple example to learn backtracking produced by Tail Recursion

Tail Recursion allow you to do backtracking.

Below is a simple program that prints 3 2 1 1 2 3 when n=3.

f(3) will print 3 and will call f(2) but after the call to f(2) there is print statement.
Since there are statements after recursive call such recursion is called Tail Recursion.

#include <stdio.h>
void f(int n)
{
    if(n == 0)
        return;
    printf("%3d",n);
    f(n-1);
    printf("%3d",n);
}
main()
{
    int n;
    scanf("%d",&n);
    f(n);
}

Another example that makes use of backtracking

Generate k bit binary strings without consecutive ones 
#include <stdio.h>
void rec(int a[],int l,int prev,int k)
{
    if(l == k)
    {
        int i;
        for(i=0;i<k;i++)
            printf("%d",a[i]);
        printf("\n");
        return;
    }
    if(prev == 0)
    {
        a[l]=0;
        rec(a,l+1,0,k);
        a[l]=1;
        rec(a,l+1,1,k);
    }
    else{
        a[l]=0;
        rec(a,l+1,0,k);
    }
       
}
main()
{
    int k;
    scanf("%d",&k);
    int a[k];
    rec(a,0,0,k);
}