How does one formulate a backtracking algorithm

I am new to learning algorithms.
I was reading backtracking algorithm for generating all strings for n bits.
If I dry run the program I know the program is giving right result.
But I didn't understood the logic can anybody please explain? What I mean is what will be be the thought process to arrive at this solution

void binary(int n)
{
    if(n < 1)
        printf("%s\n",A);    // Assume A is a global variable
    else
    {
        A[n-1] = '0';
        binary(n-1);
        A[n-1] = '1';
        binary(n-1);
    }
}

This answer begins with a first section explaining the problem in more
general terms. The direct answer to the question for the example given
by the OP is then given in a second section that illustrate the
discussion in the first.

You may well want to skip the first section and go direcly to the
second one, depending on whether you like to start with basic
principles or with the analysis of an example.

The principles : non-deterministic programming

My description is not intended for this algorithm only, but is more a
general way to design such algorithms.

The key idea is that backtracking is a technique to implement
non-determinism with depth-first exploration of the non-deterministic
space of possibilities.

Non-determinism allows you to separate the logic of the problem from
the non-deterministic exploration of the solution space. It makes
programs clearer, simplifies analysis and proofs of properties. This is
pretty much the same advantage that you get when using non-determinism
in Automata Theory, to simplify the design of automata performing a
given calculation. Non-determinism makes your technical life much easier.

This advantage is such that various programming experts and language
designers have analyzed or experimented with the introduction of a
standard non-deterministic functionality in various programming
languages, not to mention the language Prolog where non-determinism is
a central control feature.

Another advantage of using non-determinism is that it leave open the
implementation technique, that can also use breadth first exploration,
or even dynamic programming (to avoid repeating calculations). And the
handling of non-determinism, such as adding the backtrack control, is
done entirely by the compiler.

An interesting side-point is that BNF, the language of context-free
grammars, can be seen as a simple non-deterministic programming
language to write parsers. And you can compile it fairly simply into a
depth-first parser (some early ones were just that - Ned Irons, 1961),
or a breadth-first one, or a dynamic-programming one (CYK, Earley, and
some others).

However, backtracking requires mastering the state of the environment.
Without going into details, it is much easier to implement it in a
purely functional programming language that has no side-effects
(for example, no assignment to global variables), at least not in the
parts of programs that use non-determinism.

This is not in contradiction with the use of the global variable A
below, which is never read, except to collect the answers.

But it explains why I insist on starting with a recursive
non-deterministic program, rather than with an equivalent iterative
variant.

What is described below could well be done automatically by the
compiler of a non-deterministic language.

Description of the design for the given example

Here is how I would explain the design of this algorithm.

You consider an array A of bits where the permutation is stored before
printing. It can be a global variable.

First you write a non-deterministic algorithm, that will just produce
one permutation, a "random" one, chosen by the god of non-determinism
:)

This is a simple recursive procedure that ask the god's oracle
choose for each bit in succession. The choose oracle return
non-deterministically one of its arguments (here the word oracle is
used in its mythological sense, not in the usual sense of
computability theory). Using recursion is important, as I shall explain later.

void binary(int n)
{
    if(n < 0)
        printf("%s\n",A);    // Assume A is a global variable
    else
    {
        A[n-1]= choose('0','1')
        binary(n-1);
    }
}

You should agree that this algorithm will return one of the
permutation, anyone of them. You could organize the recursion differently, it does not really matter. All that matters is that you may follow any of the possible computations.

What you have done with this program is to prepare for all choices
that will make a permutation.

Then, instead of making one choice non deterministically, you simply
try them all, one after the other, for each of the calls.

Since you have a list of the possible choices (there can be a variable
number of them), you just try them in succession. You can do that by
having a segment of code for each possible value. But when the
possible values are in a list of variable length, you can just loop
over that list.

Here you have just 2 values, so you just write twice the same code,
once for each of the values, so that:

A[n-1]= choose('0','1')
        binary(n-1);

becomes

A[n-1]= '0'
        binary(n-1);
        A[n-1]= '1'
        binary(n-1);

The first call to binary will produce all permutations with '0' in
position n and the second all permutations with '1'.

Instead of choising arbitrarily, you do one, then the other.

There is an invisible trick that helps you. This would be somewhat
harder if you had used an iteration rather than a recursion.

StackExchange Computer Science Q#41601, answer score: 6