Functional Programming without recursion?

I'm really interested in functional programming and I've been learning about it for a while a quite a while now but I've hit a subject which has left me stumped. That is recursion. I mean fucking hell, I can't figure it out! When I was learning how to code I was seeing nothing but for loops in other peoples code so that's how I do things. For loops everywhere! Hell I barely know how to use a while loop. Can someone tell me if there's a point to functional programming without recursion? Can you use iteration? Maybe you can explain recursion or link me to good examples because I sure haven't come across any.

>>4
That's not always true, and you know it. Any decent functional language has proper tail calls, which lets you express iterative algorithms recursively and in constant space, retaining the mathematical purity and beauty.
>>1
Can you use iteration?
If your language implements proper tail calls (which is what most functional languages do), sure!
Take your usual factorial reduction example,

(define (fact n)
 (if (zero? n) 1
     (* n (fact (- n 1)))))

(fact 5)
This is reduce exactly like >>7's:

(fact 5)
(* 5 (fact 4))
(* 5 (* 4 (fact 3)))
(* 5 (* 4 (* 3 (fact 2))))
(* 5 (* 4 (* 3 (* 2 (fact 1)))))
(* 5 (* 4 (* 3 (* 2 (* 1 (fact 0)))))) ; base case, stop there
(* 5 (* 4 (* 3 (* 2 (* 1 1)))))
(* 5 (* 4 (* 3 (* 2 1))))
(* 5 (* 4 (* 3 2)))
(* 5 (* 4 6))
(* 5 24)
120
This is bad, just like >>9 said, because the space it takes on ``the stack'' will grow linearly as our `n' gets bigger. In some implementations, this may result in a stack overflow.

The usual iterative way to write the factorial is:

factorial(N) {
  result = 1;
  while (N > 0) {
    result = result * N
    N = N - 1
  }
  return result;
}

We have N and an accumulator, and we:
• Multiply N to the accumulator.
• Subtract 1 to N
• Iterate again until N is 0.
And return the accumulator.

Now let's write it recursively

(define (fact-iter n result)
 (if (zero? n) result ; base case, N is zero, return the accumulator
     (fact-iter (- n 1)
                (* result n)))) ; recurse (iterate) with result = N * result, and N = N -1
Note that the last thing that fact-iter does, is to recursively call itself. This is called tail recursion and is how you do looping in FP. Think of it as ``replace the argument and jump to the beginning of the function''.
Now, the reduction will look something like this:

(fact-iter 5 1) ; n = 5, result = 1
(fact-iter (- 5 1) (* 5 1))
(fact-iter 4 5) ; we replaced the arguments, jump to the top
(fact-iter (- 4 1) (* 4 5))
(fact-iter 3 20)
(fact-iter (- 3 1) (* 3 20))
(fact-iter 2 60)
(fact-iter (- 2 1) (* 2 60))
(fact-iter 1 120)
(fact-iter (- 1 1) (* 1 120))
(fact-iter 0 120) ; base case, return the accumulator
120

Further reading: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2