Comments

  • This is the title of a discussion about self-reference
    At the risk of my missing the point here, self-reference in a programming context is definitely handy. On the subjective side, several computing problems (e.g. path-finding, tree-traversal, searching) are more concisely and/or clearly written in a recursive fashion*. More concretely though, self-reference is essential for making radiation-hardened quines.

    Regular quines are fixed points of a programming language; programs which when executed can print their source code without reflection (i.e. without needing to be able to read their source code from the hard-disk).

    Radiation hardened quines are similar, but are also robust to the removal of one character. This is a useful property in environments where bits can be flipped/damaged on a regular basis (e.g. code on satellites - which are not shielded by the atmosphere); the program can repair itself.

    * Here's an example comparing an iterative vs. recursive implementation of the factorial function:
    # Iterative
iterative_factorial( x ):
  x_factorial = 1
  while x > 1:
      x_factorial *= x
      x -= 1
  return x_factorial

# Recursive
recursive_factorial( x ):
  return 1 if x == 0 else (x * recursive_factorial(x-1))
    Full disclosure, the iterative function could be written more compactly than it is above depending on the language - but using just regular language features, the recursive solution is more easily made concise.

    As another example, writing a method to navigate a maze is naturally suited to recursion.
    You could write this algorithm in an iterative form, but the recursive way below seems more intuitive to me.

    # This function prints the path to the exit, if there is one.
navigate( maze, path_taken ):

  current_position = get_position(maze, path_taken)
  past_positions = [get_position(maze, path_taken[:n]) for n in len(path_taken)]
  if current_position not in past_positions:

    if AT_EXIT: 
     print( path_taken )
     exit_program()

    else:
     if CAN_GO_STRAIGHT:
         navigate(maze, path_taken + [ STRAIGHT ])
     if CAN_GO_LEFT: 
         navigate(maze, path_taken + [ LEFT ])
     if CAN_GO_RIGHT: 
        navigate(maze, path_taken + [ RIGHT ])
Home » Zoldy