LaTeX \newcommand recursion gets very slow

Let's see what happens when you do \gcdab{377}{233}. The first expansion becomes

\ifnum233=0 \else\gcdab{233}{\modab{#1}{#2}}\fi

The conditional is false, so you get

\gcdab{233}{\modab{377}{233}}\fi

that becomes

\ifnum\modab{377}{233}=0 0 \else\gcdab{\modab{377}{233}}{\modab{233}{\modab{377}{233}}}\fi\fi

and so on, always carrying over the still uncomputed numbers.

Just by way of example, I tried \gcdab{13}{8} with \tracingmacros=1; I report here just the lines about expansions of \gcdab, which confirm what I claimed above. (Note: I removed the \relax after 0 in the \ifnum lines: it's not needed so long as you leave a blank space, or endline, after 0; it's actually bad programming style to add it, because it leaves a bunch of unwanted \relax tokens in the input stream).

\gcdab #1#2->\ifnum #2 = 0 #1\else \gcdab {#2}{\modab {#1}{#2}}\fi
#1<-13
#2<-8

\gcdab #1#2->\ifnum #2 = 0 #1\else \gcdab {#2}{\modab {#1}{#2}}\fi
#1<-8
#2<-\modab {13}{8}

\gcdab #1#2->\ifnum #2 = 0 #1\else \gcdab {#2}{\modab {#1}{#2}}\fi
#1<-\modab {13}{8}
#2<-\modab {8}{\modab {13}{8}}

\gcdab #1#2->\ifnum #2 = 0 #1\else \gcdab {#2}{\modab {#1}{#2}}\fi
#1<-\modab {8}{\modab {13}{8}}
#2<-\modab {\modab {13}{8}}{\modab {8}{\modab {13}{8}}}

\gcdab #1#2->\ifnum #2 = 0 #1\else \gcdab {#2}{\modab {#1}{#2}}\fi
#1<-\modab {\modab {13}{8}}{\modab {8}{\modab {13}{8}}}
#2<-\modab {\modab {8}{\modab {13}{8}}}{\modab {\modab {13}{8}}{\modab {8}{\modab {13}{8}}}}

\gcdab #1#2->\ifnum #2 = 0 #1\else \gcdab {#2}{\modab {#1}{#2}}\fi
#1<-\modab {\modab {8}{\modab {13}{8}}}{\modab {\modab {13}{8}}{\modab {8}{\modab {13}{8}}}}
#2<-\modab {\modab {\modab {13}{8}}{\modab {8}{\modab {13}{8}}}}{\modab {\modab {8}{\modab {13}{8}}}{\modab {\modab {13}{8}}{\modab {8}{\modab {13}{8}}}}}

Here's a version that always expands until getting an explicit number. And is fully expandable, contrary to David's.

\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{etoolbox}

\makeatletter
\newcommand*{\programmerdiv}[2]{%
  \ifnum #1 = 0
    \expandafter\@secondoftwo
  \else
    \expandafter\expandafter\expandafter\@firstoftwo
  \fi
  {\the\numexpr (2*#1 - #2) / (2 * #2) \relax}%
  {0}%
}
\newcommand*{\modab}[2]{%
  \the\numexpr #1 - \programmerdiv{#1}{#2} * #2 \relax
}
\newcommand*{\gcdab}[2]{%
  \ifnum #2 = 0
    \expandafter\@secondoftwo
  \else
    \expandafter\expandafter\expandafter\@firstoftwo
  \fi
  {\expanded{\noexpand\gcdab{#2}{\modab{#1}{#2}}}}%
  {#1}%
}
\makeatother

\begin{document}

\gcdab{37745585}{55555555}

\end{document}

I tried doing the computation 10000 times and the program ran for 1 second on my machine.

Here's the analogous report in the log file for \gcdab{13}{8} with \tracingmacros=1

\gcdab #1#2->\ifnum #2 = 0 \expandafter \@secondoftwo \else \expandafter \expandafter \expandafter \@firstoftwo \fi {\expanded {\noexpand \gcdab {#2}{\modab {#1}{#2}}}}{#1}
#1<-13
#2<-8

\gcdab #1#2->\ifnum #2 = 0 \expandafter \@secondoftwo \else \expandafter \expandafter \expandafter \@firstoftwo \fi {\expanded {\noexpand \gcdab {#2}{\modab {#1}{#2}}}}{#1}
#1<-8
#2<-5

\gcdab #1#2->\ifnum #2 = 0 \expandafter \@secondoftwo \else \expandafter \expandafter \expandafter \@firstoftwo \fi {\expanded {\noexpand \gcdab {#2}{\modab {#1}{#2}}}}{#1}
#1<-5
#2<-3

\gcdab #1#2->\ifnum #2 = 0 \expandafter \@secondoftwo \else \expandafter \expandafter \expandafter \@firstoftwo \fi {\expanded {\noexpand \gcdab {#2}{\modab {#1}{#2}}}}{#1}
#1<-3
#2<-2

\gcdab #1#2->\ifnum #2 = 0 \expandafter \@secondoftwo \else \expandafter \expandafter \expandafter \@firstoftwo \fi {\expanded {\noexpand \gcdab {#2}{\modab {#1}{#2}}}}{#1}
#1<-2
#2<-1

\gcdab #1#2->\ifnum #2 = 0 \expandafter \@secondoftwo \else \expandafter \expandafter \expandafter \@firstoftwo \fi {\expanded {\noexpand \gcdab {#2}{\modab {#1}{#2}}}}{#1}
#1<-1
#2<-0

---

The mandatory expl3 implementation:

\documentclass{article}

\ExplSyntaxOn

\NewExpandableDocumentCommand{\gcdab}{mm}
 {
  \dkozl_gcdab:nn { #1 } { #2 }
 }

\cs_new:Nn \dkozl_gcdab:nn
 {
  \int_compare:nTF { #2 = 0 }
   { #1 }
   { \dkozl_gcdab:ne { #2 } { \int_mod:nn { #1 } { #2 } } }
 }
\cs_generate_variant:Nn \dkozl_gcdab:nn { ne }

\ExplSyntaxOff

\begin{document}

\gcdab{37745585}{55555555}

\end{document}

In the first version you want to evaluate \modab earlier

\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{etoolbox}

\makeatletter
\newcommand*{\programmerdiv}[2]{%
    \ifnum #1 = \z@
        0%
    \else
        \the\numexpr (2*(#1) - (#2)) / (2 * (#2)) \expandafter\relax
    \fi
}
\newcommand*{\modab}[2]{%
    \the\numexpr #1 - \programmerdiv{#1}{#2} * (#2) \relax
}
\newcommand*{\gcdab}[2]{%
    \ifnum #2 = \z@
        #1%
    \else
        \edef\z{\noexpand\gcdab{#2}{\modab{#1}{#2}}}\z
    \fi
}

\def\afterfi#1\fi{\fi#1}

\begin{document}

\gcdab{377}{233}

\end{document}