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.

Recursion is simply the act of a function directly calling itself from within that same function.

bool bar(int n) {
   if(n > 0) {
      return bar(n - 1);
   }
   else {
      return true;
   }
}
Recursion creates nesting: all previous iterations are self-contained islands on the stack and any variables available to the most current version of the function are unique (bar "pass by reference").  All previous iterations of the function remain valid and you will have to pass control back through them to restore normal flow control at some point.  For example, the above code will call itself for as many integers above zero as is its initial input; ultimately, the input will be equal to 0 during one self-call, and the stack will unravel:
bar(5)
   bar(4)
      bar(3)
         bar(2)
            bar(1)
               bar(0)
                  true
               true
            true
         true
      true
   true
true
Use recursion lightly.  It creates stress on your stack due to the excess of frames that may be needed.

>>2

Thanks.

So if I'm understanding this recursion keeps calling itself until it has a value. When it has that value it goes up the stack? So essentially it's like calling the function twice? Once without the value, just telling the computer to come back to it once it has a value. And once it actually has the value? MIND FUCK MIND FUCK

Recursion pros:
1. More elegant than iterative counterpart
2. Easier to read

cons:
1. Harder to think about because humans don't naturally think recursively
2. More computationally intensive than iterative counterpart

Iteration pros:
1. Easier to think about
2. Less intensive than recursion

cons:
1. Harder to read compared to recursive version

>>3
That was just an example of control. Like iterative looping structures, a recursive function is generally written when program logic determines that some variable has achieved an intended or baseline value.  Finishing with a return is optional as any finished function restores control flow back to the frame that called it anyway, but that is the main way volatile information gets passed backwards up a recursive call stack.  You should be able to rewrite any recursion as a normal loop; in some languages, that immensely reduces overhead while in others its barely a worth a hiccup.

So essentially it's like calling the function twice?
It's like explicitly calling a function on duplicated modified data as many times as is necessary.  The original data is retained and you were able to prove something by processing it repeatedly.

>>1
It's not hard. At the end of your loop, simply re-visit the entry point with new parameters (eg. i + 1). That's all a for loop does for you anyway, except there's no push. With tail calls the push is optimized away so it compiles to iteration.

Here's a factorial example in Haskell:

fact 0 = 1 -- this is the base case - when you reach this, you know you're done
fact n = n * fact (n - 1) -- general rule - apply it until you reach the base case

Here's how this is evaluated:

fact 4
4 * fact 3
4 * (3 * fact 2)
4 * (3 * (2 * fact 1))
4 * (3 * (2 * (1 * fact 0)))
4 * (3 * (2 * (1 * 1)))
4 * (3 * (2 * 1))
4 * (3 * 2)
4 * 6
24

Also, you should try to use higher-order functions like map, filter and fold* instead of recursion whenever possible.

Thanks a lot for the examples /prog/. This has cleared a couple things up.

>>7

that's a shitty example. it'll overflow with larger numbers. if you want to teach someone functional programming, do your own reading first.

>>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

>>9
No it won't because the evaluation is deferred.

>>10
I don't think you fully comprehend recursion.

>>12
I don't think you fully comprehend proper tail calls.

>>11
My bad. I'm wrong.  I looked at again. You're right. That is a shitty example.

>>13
I don't think you fully comprehend how to remove a bra from a girl.

>>9
I don't think OP needs to worry about tail recursion yet, I was just showing the basics of recursion.

>>16
He'll grow thinking that recursion is inefficient, bad and harmful and ``just use a for loop'' if nobody explains him (at least) TR now.

>>15

Grab straps on the back by those little connecting pieces (whatever the fuck they're called)
Pull them inward on the horizontal (making them tighter, but separating the hooks from each other)
When hooks are sufficiently away from each other, separate on the y-axis, that is, the axis between you and the girl.

MORE LIKE
FICTIONAL PROGRAMMING
WITHOUT EXCURSION
AMIRITE LOLLLLLLLLLLLLLLLLLLLLLLLZzz!!11oNE!!1ONE1!

>>4
Or is it