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

## 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

## 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

#### 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>

 Surveying Software Supply Chain Security16/03/2023Chainguard, the co-creator of Sigstore, has conducted a survey to better understand if and how software supply best practicesare utilized by the industry. We take a look at the findings. + Full Story JetBrains Qodana Adds Taint Analysis For PHP07/03/2023Qodana Code Quality platform detects and flags programming errors such as bugs, security vulnerabilities, anomalous code, dead code and the like. Now it adds Taint analysis support too. + Full Story More News