2 questions with recursion

I got two questions about recursion.

1.

let rec mult n m =
 if n = 0 then 0
 else m + (mult (n-1) m)

How exactly does that work? I can't seem to understand it.

2.
How would I remove the last element from a list using recursion (and O'Caml):

# butLast [1; 2; 3; 4];;
- : int list [1; 2; 3]

Anyone knows how I could do it? Thanks.

[ndogg]

To understand the first one, think about your elementary multiplication. Ask yourself how it works. Now look back at your code.

If you think recursion like that is strange, think about recursion and addition: if you were given a 'zero', a function to test for zero, a successor function and a predecessor function, how could you do addition?

The other thing to think about when thinking about recursion is, can you make it tail recursive? If you can make tail recursive, a good compiler/interpreter will recognize this and actually turn it into a loop instead. Whenever you need recursion, you should always see if you can make it tail recursive.

I can't answer the second question as I do not know enough about O'Caml to answer the question.

I don't even know what tail recursive is. And I can't "tell" the first function.

If n is 0, then return 0, else, add the current value of m with the value of the function mult given paramters n-1 and m. This is seriously messing with my head... Recursion can be such a pain at times. A good ol' loop would be so much better IMO.

[Feztaa]

Recursion is a screwy concept, but it's really cool once you get it figured out (it's a lot like object oriented programming in that way -- hard to get at first, but once you get it, it's cool)

As for number one, just walk through what it's doing:

You call it with two numbers, n and m. If n is zero, it returns zero, but if n is not zero, it returns m + m + m + m (n times, or in other words, m * n).

basically, it adds m to m, and then subtracts 1 from n. Then it does that over and over until n is 0, and the end result is that m is multiplied by n.

As for number two: I don't know any ocaml, but the recursive logic is still the same.

What you need to do is write a function that will return it's first argument, and then call itself with all but the first argument (trust me on this), until there is only one argument left, at which point it does nothing. Here is some m4 code (m4 is a macro language that lends itself highly to recursion, you'll have to port to ocaml on your own)

define(`shorten', `ifelse(len(`$2'), 0, `', `$1, shorten(shift($@))')')

Anyway, the function is relatively simple: If there is a second argument, output the first argument, and then run itself again on the second and following arguments, otherwise do nothing.

So when called with the arguments "one", "two", and "three", it will output "one" and "two", simply because it doesn't output the last argument when it sees there are no more argument.s

Hope this helps.

[ndogg]

I don't even know what tail recursive is. *And I can't "tell" the first function.

If n is 0, then return 0, else, add the current value of m with the value of the function mult given paramters n-1 and m. *This is seriously messing with my head... *Recursion can be such a pain at times. *A good ol' loop would be so much better IMO.

Argh!! *You've been programming for too long in procedural languages!! *Recursion is definitely cool and something you can never completely understand. There are so many things you can do with recursive logic that are much more difficult in iterative logic. *While it is true that you can convert nearly any recursive algorithm to an iterative algorithm, it is not true that the iterative version is necessarily better or more optimized. *Often times, when you convert a recursive solution to an iterative solution, there are many cases in which you end up doing nothing more than what the compiler or interpretter would have done anyways with the recursive solution (i.e. pushing stuff on a stack.)

I read somewhere, the following which I thought did a very good job of illustrating recursion in very simple terms:

A child couldn't sleep, so her mother told her a story about a little frog,
 ****who couldn't sleep, so the frog's mother told her a story about a little bear,
 ******** who couldn't sleep, so the bear's mother told her a story about a little weasel... 
************who fell asleep.
 ********...and the little bear fell asleep;
 ****...and the little frog fell asleep;
 ...and the child fell asleep.

I want you to perform an experiment, that hopefully will help you to understand recursion. *Get two rather large mirrors and have them face each other (with enough distance so that you can walk between them.) *What you see is a real life example of recursion in the real world.

The other thing to do is to go look at a few MC Escher paintings. *Many of his paintings are, in a sense, recursive in nature. *They are beautiful paintings that will throw your head against the wall just so you can try to understand them.

PS Once you understand recursion, I'll be happy to explain tail recursion. *It's difficult to understand tail recursion if you do not understand recursion.

I got the solution for my second question:

open List;;

let rec butLast l =
 if tl l = [] then []
 else hd l :: butLast (tl l)

Ok, Vince, I don't know if I'm gonna be able to make you understand recursion, but I'll try.

Basically, believe it or not, recursion is a tool to make things easier to understand than if you used an iterative method. If you're solving a problem and you notice that you're performing the same sequence of operations on each problem, then recursion is perfect.

If you know mergesort or quicksort, I think they're perfect examples to make you understand recursion.

Another thing to note is that it's generally a bad idea to use recursion to solve math functions, because let's say if you were multiplying 1000000^99 by 99999^9235, then you'd have a lot of recursive stacks and risk stack overflowing.

What's tail recursion? In short, if your recursive solution can obviously be solved by a simple while loop, then chances are your solution has tail recursion.

Why is recursion good? Because for certain problems (mind you, there are people out there who will go out of their way to make their frickin' toaster to work recursively and tell you it's more efficient), recursion is ideal and can be easier to read code-wise.

Recursion in a way is like magic, because if you try and understand a recursive solution the way you'd understand an iterative solution, then you're doing the wrong thing. Recursion does all that work for you! In fact, that's the point to recursion, let the complicated details get handled by the computer, but ALWAYS make sure you have a base case, but that goes without saying.

ton poste, ton poste...

Another thing to note is that it's generally a bad idea to use recursion to solve math functions, because let's say if you were multiplying 1000000^99 by 99999^9235, then you'd have a lot of recursive stacks and risk stack overflowing.

Fear not. The antive-code compiler of O'Caml has no stack limit. You can infinitely call a function without problems.

[ndogg]

I should clarify tail recursion a little more.

Tail recursion means that a recursive call happens last in a recursive function and no other data relies on the return value of the recursive call.

E.g.

let mult n m =
  let rec accrue n accum =
   if n = 0 then accum
   else (accrue (n-1) (accum+m))
  (accrue n 0)
(* This is tail recursive where as yours is not. This will likely be optimized by whatever interpreter or compiler you use. *)

GnuVince, do you understand recursion yet? Are you confident in it? Recursion is so crucial to programming that to not understand it is very limiting.

Yeah I do. *But I do not think it's so crucial to programming though. It's a good thing to know, but I don't think you're limited if you don't use it.