My first exposure to functional concepts was, doh, mathematics! Functions are maps, not procedures that flip bits. There recursive definitions and such. Inductive proofs. The activity of doing derivation: you leave the old formula as is, and produce a new one from it by applying rules, which you should recognize as a kind of function.<p>Some of this stuff, you play with in "Blub" imperative languages. If you write a recursive factorial or fibonacci in Pascal, that's functional programming. Just not with higher order functions.<p>The C preprocessor is an example of functional calculation. (Though macros can be undefined and redefined, mainly they are just defined and called, and perform substitutions without clobbering anything.)<p>Unix pipelines : don't clobber anything other than the file being created or replaced at the end.<p>Parsing a grammar with Yacc and building a tree: basically functional. The imperative bits going on are hidden under the hood. $$ = make_node($1, $3) is an assignment, but it's boiler-plate; you don't think of it as assignment, but yielding the semantic value of the rule, which is constructed from the pattern-matched $1 and $3 pieces.<p>All those things teach you that it's useful and good to calculate a new value from an existing one, while leaving the original alone.<p>There is a lot of functional programming in the middle of imperative programming. E.g. constructing a balanced binary tree might not be functional (it can be, but often isn't in Algol-like languages), the queries on that structure are conductive to functional programming. Queries don't mutate the structure, and if recursion is used, don't mutate traversal variables.<p>A binary search of an array can be coded functionally via recursion.<p>Here is a functional version of strchr in C:<p><pre><code> const char *strchr(const char *str, int ch)
{
return (*str == 0) ? 0
: *str == ch ? str
: strchr(str + 1, ch);
}
</code></pre>
Lisp was something that clicked almost instantly. I came to that armed with a lot of experience and understanding, and was well-versed in recursion, plus all around systems programming as an experienced developer. The idea that, say, a tree could be recursively defined as a null value, or else a node with two children, was nothing new. Or that a recursive function could search that.