Programmer's Guide To Theory - What Is Recursion
Written by Mike James   
Monday, 02 August 2021
Article Index
Programmer's Guide To Theory - What Is Recursion
Self-Reference
Forward And Backward

theoryicon

Forward and Backward Recursion

In general a recursive object looks something like:

Function xxx(parameters)
  list of instructions 1
if condition then Call xxx
  list of instructions 2
Return

The first list of instructions is obeyed on the way up the spiral, i.e. as the instances of the function are being built, and the second list is obeyed on the way back down the spiral as the instances are being destroyed. You can also see the sense in which the first list occurs in the order you would expect, but the second is obeyed in the reverse order that the functions are called in.

This is one of the reasons that recursion is more than just a simple loop. A loop just goes in one direction, but recursion goes up the chain of calls and then back down again.

Sometimes a recursive function has only the first or the second list of instructions and these are easier to analyze and implement. For example a recursive function that doesn't have a second list doesn't need the copies created on the way up the recursion to be kept because they aren't made any use of on the way down! This is usually called tail recursion because the recursive call to the function is the very last instruction in the function, i.e. in the tail end of the function. Many languages can implement tail recursion more efficiently than general recursion because they can throw away the state of the function before the recursive call, so saving stack space.

So tail recursion is good because it can be efficiently implemented, but you can see that limiting yourself to tail recursion is missing some of the power of recursion because it only has a forward order of execution like a simple loop.

In book but not in this extract:

  • What Use is Recursion?
  • A Case for Recursion -The Binary Tree
  • Nested Loops
  • The Paradox of Self-Reference

 

Summary

 

  • The simplest way of repeating anything is to use a loop and the shape of the flow of control is indeed just a loop.

  • There are conditional loops and enumeration loops but the only type of loop you need is the conditional loop.

  • Recursion, or self-reference, is another way of repeating things. It isn't a necessary construct as it can be emulated using loops, but it is very useful.

  • Infinite recursion is the equivalent of an infinite loop.

  • The most important idea in recursion is that a complete copy of a function is brought into existence with each recursive call.

  • You can think of the flow of control in recursion as a spiral moving up each time the function is called and then spiraling down as each function completes.

  • The block of code before the recursive call is executed on the way up the spiral and the block of code after the recursive call is executed on the way down the spiral.

  • If the block of code after the recursive call is eliminated we have tail recursion, which is efficient to implement.

  • Recursion can be useful when implementing an algorithm that has a common recursive definition. It is more necessary, however, when the data structure is itself recursive.

  • Recursion is the easiest way to implement a variable number of nested loops and this is also the reason why recursive algorithms are exponential.

  • Many paradoxes arise from contradictory self-reference, which can be thought of as infinite recursions. The result of an infinite recursion is undecidable and all of the paradoxes of computer science are infinite recursions.

  • Recursion is an example of self-reference which lends itself easily to mysticism and is often called a strange loop. Human consciousness is the result of us observing us, which in turn is an example of the universe observing itself, a strange loop that goes beyond the scope of this book

A Programmers Guide To Theory

Now available as a paperback and ebook from Amazon.

cover600

Contents

  1. What Is Computer Science?
    Part I What Is Computable?
  2. What Is Computation?
  3. The Halting Problem 
  4. Finite State Machines
    Extract 1: Finite State Machines
  5. Practical Grammar
  6. Numbers, Infinity and Computation
    Extract 1: Numbers 
    Extract 2: Aleph Zero The First Transfinite
    Extract 3: In Search Of Aleph-One
    Extract 4: Transcendental Numbers ***NEW!
  7. Kolmogorov Complexity and Randomness
    Extract 1:Kolmogorov Complexity 
  8. Algorithm of Choice
  9. Gödel’s Incompleteness Theorem
  10. Lambda Calculus
    Part II Bits, Codes and Logic
  11. Information Theory 
  12. Coding Theory – Splitting the Bit
  13. Error Correction 
  14. Boolean Logic
    Part III Computational Complexity
  15. How Hard Can It Be?
    Extract 1: Where Do The Big Os Come From 
  16. Recursion
    Extract 1: What Is Recursion
    Extract 2: Why Recursion
  17. NP Versus P Algorithms
    Extract 1: NP & Co-NP
    Extract 2: NP Complete 

<ASIN:1871962439>

<ASIN:1871962587>

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Banner


Python 3.11 Goes Faster
08/06/2022

Python doesn't do a bad job of being fast given how sophisticated it is, but it seems it is about to do a whole lot better according to independent benchmarks. Version 3.11 incorporates many of the ch [ ... ]



Python Is Everywhere - 2021 Survey Results
08/06/2022

The results of the 2021 Python Developers Survey, conducted as a collaborative effort between the Python Software Foundation and JetBrains have been published. We take a look.


More News

pythondata

 



 

Comments




or email your comment to: comments@i-programmer.info

 



Last Updated ( Tuesday, 03 August 2021 )