Base case in a recursive method

Question

A theoretical question here about the base or halting case in a recursive method, what's its standards?

I mean, is it normal not to have body in it, just a return statement?

Is it always like the following:

if (input operation value)
    return sth;

Do you have different thoughts about it?

score 13 · Answer 1 · answered May 06 '10 at 18:05

13

The pattern for recursive functions is that they look something like this:

f( value ) 
   if ( test value )
      return value
   else
      return f( simplify value )

I don't think you can say much more than that about general cases.

answered May 06 '10 at 18:05

1

Which programming language is that? – Solace Oct 03 '15 at 17:03
6

@Solace That looks more like a pseudocode, not any particular programming language – Deep Jan 10 '16 at 03:11
This is by far the best way to explain recursive methods. I used this approach for merging two linked list implementation. – Ming Huang Jul 14 '19 at 23:59

score 4 · Answer 2 · answered May 06 '10 at 18:03

4

The base case is to terminate the loop (avoid becoming an infinite recursion). There's no standard in the base case, any input that is simple enough to be solved exactly can be chosen as one.

For example, this is perfectly valid:

int factorial (int n) {
  if (n <= 5) {
    // Not just a return statement
    int x = 1;
    while (n > 0) {
      x *= n;
      -- n;
    }
    return x;
  } else {
    return n * factorial(n-1);
  }
}

answered May 06 '10 at 18:03

kennytm

510,854
105
1,084
1,005

1

I said that I'm asking a theoretical question, I mean if I want to teach recursion, I wont use your previous code, I know it's a valid way, but it doesn't make recursion and the Base case concept clear enough, what do you think? – Lisa May 06 '10 at 18:12

score 1 · Answer 3 · edited Feb 14 '18 at 14:44

1

In some cases, your base case is

return literal

In some cases, your base case is not simply "return a literal".

There cannot be a "standard" -- it depends on your function.

The "Syracuse Function" http://en.wikipedia.org/wiki/Collatz_conjecture for example, doesn't have a trivial base case or a trivial literal value.

"Do you have different thoughts about it??" Isn't really a sensible question.

The recursion has to terminate, that's all. A trivial tail recursion may have a "base case" that returns a literal, or it may be a calculation. A more complex recursion may not have a trivial "base case".

edited Feb 14 '18 at 14:44

John Topley

113,588
46
195
237

answered May 06 '10 at 18:18

S.Lott

384,516
81
508
779

Trying to build further upon this answer, a base case in a recursive function could also be something whose `O(n)` is substantially lower than the `O(n)` of the actual function. Hence returning a simpler (less complex) operation. – Deep Jan 10 '16 at 03:14

score 0 · Answer 4 · answered May 06 '10 at 18:07

0

It depends entirely on the particular recursive function. In general, it can't be an empty return; statement, though - for any recursive function that returns a value, the base case should also return a value of that type, since func(base) is also a perfectly valid call. For example, a recursive factorial function would return a 1 as the base value.

answered May 06 '10 at 18:07

tzaman

46,925
11
90
115

A recursive method doesn't have to return a value, though. – Ken May 06 '10 at 18:27
True, of course. But then, I could say: for recursive methods that return `void`, the base will also return `void` ... ;) – tzaman May 06 '10 at 18:33

Base case in a recursive method

4 Answers4

Linked