Recursive function best practices; What are they?

Question

What are some other language independent ways of designing recursive functions other than the typical:

if (counter < 1) 
    return output;
else
   callSelf(); 

Do other methods even exist? Whenever viewing examples I always see a version of the code above.

Thanks! :)

Answer 1

The "best practice" is to try to use structural induction (roughly, a fold over the datastructure). If that fails, you might want to consider general (unrestricted) recursion.

For example, when working with lists, it is customary to use a fold. Many functions, such as concatenation and append are easy to describe in this fashion.

Answer 2

In lazy programming languages, you can have recursion that doesn't define an end point. The result could be an infinite data structure, but that's OK as long as you don't try to use all of it. For example, a common way to define the entire fibonacci series in Haskell is this:

fibS = 1:1: zipWith (+) fibS (tail fibS)

This translates into the following English: the Fibonacci series is 1, followed by 1, followed by the series which is the element-wise sum of the Fibonacci series and the Fibonacci series without its first element.

This sounds like a recursive definition, rather than recursive function calling, but in Haskell there is no big distinction - the above is just a 'nullary function' (one that takes no arguments).

Normally to use this, you would just use the first N elements of fibS. You can in fact use all of it (e.g. print it all), as long as you are happy with your program running forever :-)

For a more useful example of using 'all' of an infinite recursion, a web server might have a 'main loop' that runs forever defined using a recursive function that does not terminate.

EDIT: These principles can certainly be applied to other languages if some element of 'laziness' is present. Here is the above implementation of fibS ported to Python using generators:

def zipWith(func, iter1, iter2):
    while True:
        yield func(iter1.next(), iter2.next())

def tail(iter):
    iter.next()
    for x in iter:
        yield x

def fibS():
    yield 1
    yield 1
    for x in zipWith(lambda x,y: x + y, fibS(), tail(fibS())):
        yield x

# Test it by printing out the first n elements.
def take(n, iter):
    while n > 0:
        yield iter.next()
        n = n - 1

print list(take(10, fibS()))

Don't expect it to be as efficient as the Haskell version! You could make it more efficient using some hacks and global objects of some kind. But notice the lack of explicit termination conditions.

Answer 3

There are a lot of variations, for example:

foreach (child in parameter.GetChildren()) {
   callself(child)
}

or

switch (param.length) {
   case 1: return param[0];
   case 2: return param[0] + param[1];
   default: return callself(param.FirstHalf()) + callself(param.LastHalf());
}

What they all have in common is that they devide the task into smaller tasks and then uses itself to solve the smaller tasks until they are so small that they can be solved with a trivial operation.

Answer 4

Google has a lot of information on recursion. :)

Answer 5

If you want your recursion to stop, you have to put a test.

But you can have things which vary a bit, like the Hanoi Tower algorithm (2 recursive call):

int Hanoi( source, mid, destination, height ) {

if ( height == 1 ) { print source '->' destination }
else
   Hanoi ( source, destination, mid, height - 1 ) ; # move all upper tower from source to mid
   print source '->' destination;
   Hanoi ( mid , source, destination, height -1 ) ; # move all the upper tower from mid to destination

}
Hanoi ( "0", "1", "2", 8 );

Will print the solution of moving 8 discs from source to dest. See http://en.wikipedia.org/wiki/Tower_of_Hanoi for the rules of the game.

Answer 6

What exactly is your question? Just trying some answers ;-)

There are many types of recursion:

• "Standard" recursion

  let rec sum = function
      | [] -> 0
      | x::x' -> x + sum x'
  

• Tail recursion

  let rec sum acc = function
      | [] -> acc
      | x::x' -> sum (x + acc) x'
  

• Mutual recursion

   let rec f() = g()
   and g() = f()
  

• Fixed-Point recursion

  let factorial n = fix(fun rec n -> if n < 1 then 1 else n * rec (n - 1)) n
  

And the list of recursion's applications is extremely rich. In functional programming, any iterative code (for-loops etc.) is expressed through recursion!

Another good example:

let rec sumTree = function
| End -> 0
| Node(val, right, left) = val + sumTree right + sumTree left

The main "best-practice" of recursion is to make sure that your termination condition is satisfied at some point, so you'll typically self-call your function with "smaller" data than in the initial call (just one part of the tree). Everything else can result in endless recursions.

Answer 7

That's pretty much it.

Recursive function design is pretty much just as simple as "Can I return a value yet or do I need to do further processing?" and "Processing returned a value with it, what do I do to it before I pass it along?"

Tail-recursion is just an optimization method that a compiler/interpreter can use to increase performance. Essentially, if your recursive function follows a strict format (nothing happens after the recursive call, usually meaning the recursive call is always paired with the return) the recursive function can be optimized and rewritten as a for-loop.

Answer 8

Well, you need to have some method of knowing when to stop recursing. That's what your counter < 1 is, correct? I frequently remove / add items to a list, traverse down trees, and perform mathematical functions while recursing. Ultimately, you need to know when to stop recursing and when not to, so I don't see any other options that can't be boiled down to counter < 1.

function ProcessNode(node)
  //Do stuff
  while (node.Next != null)
    ProcessNode(node.Next);

function ManipulateList(list)
  //Do stuff, adding and removing items based on logic
  if (testCondition)
    return;
  else
    ManipulateList(list);