I've done some research on the history of programming languages.
But first, lets see what Wikipedia says about structured programming:
Structured programming is a programming paradigm aimed on improving the clarity, quality, and development time of a computer program by making extensive use of subroutines, block structures and for and while loops—in contrast to using simple tests and jumps such as the goto statement which could lead to "spaghetti code" which is both difficult to follow and to maintain.
And that, of course, includes the use of recursive functions.
From History of Lisp (written by McCarthy. Bold emphasis mine):
As a programming language, LISP is characterized by the following ideas: ..., the recursive use of conditional expressions as a sufficient tool for building computable functions, ...
Towards the end of the initial period, it became clear that this
combination of ideas made an elegant mathematical system as well
as a practical programming language. Then mathematical neatness became
a goal and led to pruning some features from the core of the language.
This was partly motivated by esthetic reasons and partly by the
belief that it would be easier to devise techniques for proving
programs correct if the semantics were compact and without exceptions.
I invented conditional expressions in connection with a set of chess legal move routines I wrote in FORTRAN for the IBM 704 at M.I.T. during 1957-58. This program did not use list processing. The IF statement provided in FORTRAN 1 and FORTRAN 2 was very awkward to use, and it was natural to invent a function XIF(M,N1,N2) whose value was N1 or N2 according to whether the expression M was zero or not. The function shortened many programs and made them easier to understand, but it had to be used sparingly, because all three arguments had to be evaluated before XIF was entered, since XIF was called as an ordinary FORTRAN function though written in machine language. This led to the invention of the true conditional expression which evaluates only one of N1 and N2 according to whether M is true or false and to a desire for a programming language that would allow its use.
A paper defining conditional expressions and proposing their use in Algol was sent to the Communications of the ACM but was arbitrarily demoted to a letter to the editor, because it was very short.
From The Advent of Recursion & Logic in Computer Science:
Since FORTRAN did not contain recursion either, he(McCarthy) tried to add it to the language, but without success.
In August 1959, McCarthy wrote a letter in which he openly advocated for recursive procedures [80], and, in January 1960, at the final ALGOL60 Paris conference, McCarthy suggested to add recursive procedures to the ALGOL60 language [116, p.30].
Perlis even stated in 1978 with respect to the ALGOL Effort that:
"The implications of recursion were not really understood, except by McCarthy." [91, p.160]
To summarize, he had not only thought recursive functions and conditional expresions are sufficient for building computable functions, but also believed they would lead to a readable and easy to verify code, and spread the idea to other languages.
Therefore, even though McCarthy didn't say goto is harmful, I think he is the first one to perceive the importance of structured programming and Lisp is the first language that can be called structured programming language. (Fortran I didn't even support subroutines or nested expressions, and only had an arithmetic if statement)
