Here is my extremly basic understanding of Replace and ReplaceAll.

**This post is also a way for me to check if I understood the mechanism behind, if you see mistakes in my explanation don't hesitate to correct me !**

Replace is a function that will apply replacement rules on part of expression.

However, it will apply the replacement rules at specific level given in parameters (by default it will be {0} corresponding to the whole tree).

So here :

    Replace[x^2 + 1, x^2 -> a]

It doesn't do anything as x^2 is a subpart of the tree but it is not the whole tree in itself.

I could do :

    Replace[x^2 + 1, x^2 -> a, All]

To make it work. Then the code will look at all the levels of the trees (thus all the subtrees) and look for a matching replacement.

I could also do :

    ReplaceAll[x^2 + 1, x^2 -> a]

And here is my question : is there actually any difference between using 

    Replace[expr, rule, All]

and 

    ReplaceAll[expr,rule]

or it is indeed the same thing ?


----------

Another question linked to the answer

Then I don't understand this behavior :

    diffReplaceReplaceAll = g[g[x]];
    
    Replace[diffReplaceReplaceAll, g -> c, All]
    
    g[g[x]]
    
    g[g[x]][[1]]
    
    g[x]
    
    ReplaceAll[diffReplaceReplaceAll, g -> c]
    
    c[c[x]]

If I take strictly what you say, ReplaceAll shoud return c[g[x]]

Indeed, it goes from the outside which is g[g[x]] (the whole tree), it looks at each part. So first it tries with the Head (the 0 part), which is $g$, it replaces it by $c$. And... it should stop here right ? Thus we would have c[g[x]] as a result. But it continues and replaces the second g. Why ?

My problem is very probably linked to a not fully understanding of what a part precisely is. But if I'm not wrong the 0'th part is the head and the 1st part is g[x] here right ?

I also have a problem with Replace : why if it goes from the inside to the outside I don't have at least g[c[x]] ?

Remark : I don't fully get your example as I'm not familiar with ":>", I am reading about it now.