1

So, we all know recursive functions, right? But what exactly is it, that makes a function recursive? I had a small discussion in the comment section of another question (Lightening effect with javascript) that kind of challenged my view of recursive functions but it also left me with a quite unsatisfying lack of proper definition.

My personal definition of recursive functions so far was the following:

A function is recursive if it directly or indirectly invokes itself

Note: I will provide JavaScript code for the following examples, but I'm sure they are pretty universal.

A simple example for such a recursive function could be this:

function a() {
    a();
}

but also this:

function a() {
    b();
}

function b() {
    a();
}

or even this:

function a() {
    setTimeout(a, 1000);
}

None of those functions computes anything but I would have still considered them recursive just because they invoke themselves.

One thing that came up was, that the third example is not recursive because it uses setTimeout and therefor the stack is unwound. It also isn't recursive because after returning from the nth invocation it doesn't give back control to the n-1th invocation.

Another point, that was raised, was that none of those functions were recursive because they all don't compute an actual problem in a recursive way. Meaning that a problem has to be solved by dividing it in smaller and smaller instances. Here the quoted Wikipedia article:

Recursion in computer programming is exemplified when a function is defined in terms of simpler, often smaller versions of itself. The solution to the problem is then devised by combining the solutions obtained from the simpler versions of the problem.

So this is recursive:

function fac(n) {
    if (n <= 0) {
        return 1;
    }
    return n * fac(n - 1);
}

But this wouldn't be:

function fac(n) {
    if (n <= 0) {
        return 1;
    }
    console.log(n);
    fac(n - 1);
}

So what is the proper definition of a recursive function? Is there any at all or is it really just a philosophical question? What features must a function have, in order to be classified recursive?

Improve this question

4 Answers 4

Reset to default
2

Recursion is simply defining a problem in terms of a simpler case (simpler meaning "closer" to the terminating condition, not necessarily actually simpler) of that problem, down to the point where the simplest case is a known one (the terminating condition alluded to earlier). So, for example, the perennial factorial function has a terminating condition:

f(1) = 1

and the definition of the problem in terms of a simpler one:

f(n) = n * f(n - 1), for n > 1

The best explanation of it that I ever heard was this:

  1. If you're Donald Knuth, you understand what it is.
  2. Otherwise, find someone closer to Donald and ask them.

I wouldn't call the setTimeout one recursion because a is not actually calling itself. Instead, it's asking the "system" to call it at some later date.

It's also important to have the terminating condition in there somewhere. Without that, it's still recursion but it's infinite recursion, no different to infinite loops like:

for (i = 0; i < 10; j++) {}

and hence unlikely to be any good for anything other than testing what happens when your stack overflows :-)

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

Good ol' Knuth. I haven't heard this one yet.
So a function that calls itself, just to increase a counter to traverse a flat array, wouldn't be recursive?
@basilikum, yes it would be - it has the termination point at the end of the array and it has the function defined in terms of a "simpler" function. It's an inefficient way to do it since stack is a fairly limited resource, but it's still recursion, just like def sum (a,b) = sum (a+1,b-1) if b > 0, else a (for unsigned numbers of course). Not a smart way to add two numbers unless you can only add or subtract 1, but it's still recursion.
Ok, so then recursion is really a feature of my problem solving strategy and not of what I construct in the programming language...if that makes sense?
@basilikum, it's both a way of thinking (pure maths has the concept even where no computers are involved) and a way to implement that thinking in algorithms and languages.
|
2

Definition of Recursion? Read this line again until you get it.

(A selfcalling function with an abort criterium to prevent infinite looping).

Improve this answer

4 Comments

so if it doesn't have an abort criterium it's not recursive anymore?
"Definition of Recursion? Read this line again until you get it." - upvoting this until my mouse button breaks! :D
@basilikum It is, but it isn't useful, because it never terminates.
I actually just realize the recursion in the answer ;) Yeah, makes sense. So is calling itself really the only criterion? And what about the setTimeout example?
2

Recursion is the name that was given to function that calls itself. Now whether the function calls itself infinitely or not.. it is still a Recursion.

It is not necessarily that the problem is divided into sub-problems. However, in computer science; The term Recursion refers to a technique that is used to solve a problem, by breaking the problem into sub-problems and usually the problem is finite.

One more point, Recursion is implemented using Stack. Each function call is piled on top of the other in the stack, until the last call meets the base condition, then the functions in the stack are executed from top to bottom.

However, if there is no base condition or the base condition is never to be satisfied. then infinite calls to the function will be pushed to the stack causing the memory to be filled up and a stackOverFlow exception will be thrown and OS handles it by terminating the program.

In Regard to setTimeout() It is an asynchronous call and is not related to recursion, it is an independent call as the caller function doesn't depend on the called one whether it is the same function being called or another.

Improve this answer

Comments

0

From Wikipedia that you have posted:

Recursion in computer programming is exemplified when a function is defined in terms of simpler, often smaller versions of itself. The solution to the problem is then devised by combining the solutions obtained from the simpler versions of the problem.

So. There is a problem, and there is a solution. There is a function that call itself minimizing the main problem. This function is recursive.

Case:

function a() {
    a();
}

there is no problem, there is nothing to minimize, there is no solution. It's not recursive for me. It's just an infinite loop.

So another example:

function a(n) {
    if(n<.5) {
        return n+a(Math.random());
    }else {
        return n;
    }
}
console.log(a(.3));

Is this recursive? No. There is maybe a problem, but the solution is not found minimzing the main problem. Simple it call itself randomly until some flag is true. Again, it's a loop. The same happens with a setTimeout or setInterval (the solution of problem will depend from system call).

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.