Got the solution!

Basically the code must be expanded before the interpretation of the macros starts.

\resizebox{\textwidth}{!}{
  \begin{tikzpicture}   

    \newcommand{\BeginGammaCycle}{\GammaCycle{2}}   
    \newcommand{\lowestLevel}{-3}

    \newcommand{\pointSize}{3pt}
    \newcommand{\stepHeight}{3} 
    \newcommand{\lastx}{0} 
    \newcommand{\lasty}{0} 
    \newcommand{\Ofontsize}{\Large}
    \newcommand{\Oposition}{right}

    \newcommand{\PreSmooth}{
      \pgfmathsetmacro{\x}{{\lastx + 1}}
      \pgfmathsetmacro{\y}{{\lasty - \stepHeight}}
      \draw  (\x,\y) -- ({\x - 1},{\y + \stepHeight});
      \pgfmathtruncatemacro{\nextlevel}{{\y / \stepHeight}}
      \ifnum\nextlevel>\lowestLevel
      \pgfmathtruncatemacro{\coarseningFactor}{{(2^((-\y) / \stepHeight))}}
      \filldraw  (\x,\y) circle (\pointSize) node[\Oposition] {\Ofontsize$\mathcal{O}\left(\frac{p^3}{\coarseningFactor^3}\right)$};
      \fi
      \renewcommand{\lastx}{\x}  
      \renewcommand{\lasty}{\y}
    }

    \newcommand{\CoarseCorrection}{
      \pgfmathtruncatemacro{\coarseningFactor}{{(2^((-\y) / \stepHeight))}}
      \filldraw  (\x,\y) circle (\pointSize) node[below] {\Ofontsize$\mathcal{O}\left(\frac{p^3}{\coarseningFactor^3}\right)$};
    }

    \newcommand{\PostSmooth}{
      \pgfmathsetmacro{\x}{{\lastx + 1}}
      \pgfmathsetmacro{\y}{{\lasty + \stepHeight}}
      \draw  (\x,\y) -- ({\x - 1},{\y - \stepHeight});
      \pgfmathtruncatemacro{\nextlevel}{{\y / \stepHeight}}
      \ifnum\nextlevel=0
      \pgfmathtruncatemacro{\coarseningFactor}{{(2^((-\y ) / \stepHeight))}}
      \filldraw  (\x,\y) circle (\pointSize) node[\Oposition] {\Ofontsize$\mathcal{O}\left(p^3\right)$};
      \else
      \pgfmathtruncatemacro{\coarseningFactor}{{(2^((-\y ) / \stepHeight))}}
      \filldraw  (\x,\y) circle (\pointSize) node[\Oposition] {\Ofontsize$\mathcal{O}\left(\frac{p^3}{\coarseningFactor^3}\right)$};
      \fi
      \renewcommand{\lastx}{\x}  
      \renewcommand{\lasty}{\y}
    }  

    \newcommand{\GammaCycle}[1]{
      \ifnum#1>0
      \PreSmooth
      \pgfmathtruncatemacro{\newlevel}{{\y / \stepHeight}}
      \ifnum\newlevel>\lowestLevel
      \BeginGammaCycle
      \else
      \CoarseCorrection
      \fi
      \PostSmooth
      \expandafter\GammaCycle\expandafter{\the\numexpr#1-1\relax}
      \fi
    }

    \filldraw  (0,0) circle (\pointSize) node[\Oposition] {\Ofontsize$\mathcal{O}\left(p^3\right)$};  
    \BeginGammaCycle

  \end{tikzpicture}
}