2
$\begingroup$

I understand that factorial, as the simplest example of a function that can be defined recursively, was fairly new in Gauss' time. The exclam notation was early 19th century, I believe.

I think Gauss would have thought of factorial "iteratively" -- would not the idea of $N! = N(N-1)!$ (with base case of $0! = 1$) have been something surprising to him?

(Credit where credit is due: GitHub Copilot, in a rare departure from strict coding discussions emphasized the base case in this and agreed that Gauss would have thought of the definition iteratively/computationally.)

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
3
$\begingroup$

Gauss has articulated some notion of recursion in his work on what we today call the Cooley-Tukey Fast Fourier Transform (FFT) algorithm.

where one finds the following translated passage of Gauss's original:

And so for this case, where most of the proposed values of the function X, an Integral period of the arrangement, the number is composite and $=\pi=\mu\nu$, in articles 25, 26, we learned that through the division of that period into $\nu$ periods of $\mu$ terms, it produces, when all values are given, the same satisfactory function, which by the immediate application of the general theory applies to the whole period; truly, that method greatly reduces the tediousness of mechanical calculations, success will teach the one who tries it.

Gauss essentially describes recursion here, though the language is not explicit. That you can use the solution of a sub-problem of the same form to compute the whole was known to Gauss because indeed he would compute examples in the paper. So while his language to describe the phenomenon is indirect (i.e. there isn't a clearly formed concept of "recursion") it is understood to be part of the computation. Gauss notes that in this case this setup "greatly reduces the tediousness of mechanical calculations" which is an imprecise statement about the computational complexity of the FFT.

This work of Gauss was not published during his life-time and is generally dated around 1805.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ My personal guess is that the smartest man (or so) in history would have understood the power of recursion really fast and would have come up with the concept of the base case within the first hour perhaps. "Mechanical calculations" is a surprisingly modern term, is it not? $\endgroup$
    – releseabe
    Commented Aug 20 at 11:48
  • $\begingroup$ Concretely the text is on page 307: Pro eo itaque casu, ubi multitudo valorum propositorum functionis X, periodum integram formantium, numerus compositus est $= \pi = \mu \nu$, per partitionem illius periodi in $\nu$ periodos $\mu$ terminorum eandem functionem cunctis valoribus datis satisfacientem eruere in artt. 25, 26 didicimus, quae per applicationem immediatam theoriae generalis ad periodum totam prodiret: illam vero methodum calculi mechanici taedium magis minuere, praxis tentantem docebit. $\endgroup$
    – Patrick Stevens
    Commented Aug 20 at 22:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.