Programming with Python

Recursion does not perfectly fit into the conditionals section, but it does align nicely with loops, so here it is.

What is Recursion?

The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function. Using recursive algorithm, certain problems can be solved quite easily. Examples of such problems are Towers of Hanoi (TOH), Factorial, Fibonacci, Depth-First Search of Graphs and much more. It is said that anything using a while or for loop can be written as a recursive call.

calls itself

A base case is needed to terminate

How NOT to use it

A game is shown here where the main() function is conditionally called from within main(). If you put this code into pythontutor you can see the effect. This is a recursive call- the effect is that when you play a few rounds and then chose to exit, you are still in the game... while the player has closed the "current main" they then arrive back into the main from the previous round.... it is strange indeed, and these things happen when a recursive call is made without realising that this is what is happening.

Examples of correctly using recursion

The example shown here is a countdown. Note that with the recursive function, we start with the "end" or exit condition, and then make a call to the same function using a "smaller" variable.

iterative countdown code

recursive countdown code

There are many more useful applications some of which are in lab exercises, such as factorial and fibonacci. It can be a different mode of thinking but you will find that many problems are more easily solved using recursion than looping, and as shown in the video, using a data structure to store values can improve speed immensely.

To sum it up

Recursion is a way of solving problems via the smaller versions of the same problem. We solve the problem via the smaller sub-problems till we reach the trivial version of the problem i.e. base case.

“In order to understand recursion, one must first understand recursion.”

In other words, a recursive function is a function that calls itself until a “base condition” is true, and execution stops. The recursive function has two parts:

Base Case
Recursive Structure

Towers of Hanoi

This is a classic algorithm which can be solved much more easily with a recursive function than with a classic "for" or "while" loop. For a full explanation, check out this article on freecodecamp.

Step though the code, or re-write it yourself to get a feel for the flow. Thinking recursively take some time to get used to. In the example code above, it looks like nothing happens until we reach the base case, where there is one disk. With one disk, we just move it from the source tower to the destination. You could copy this code and replace the value 4 with any number, and it sill be solved just the same. Having only one disk is the simplest form of this problem. Having many disks os more difficult, but you will see that solving for 3 disks allows us to solve for any number of disks.

Divide and Conquer is a problem-solving strategy that involves breaking down a complex problem into smaller, more manageable parts, solving each part individually, and then combining the solutions to solve the original problem. It is a widely used algorithmic technique in computer science and mathematics.

A divide and conquer algorithm is a strategy of solving a large problem by

breaking the problem into smaller sub-problems
solving the sub-problems, and
combining them to get the desired output.

To use the divide and conquer algorithm, recursion is used.

Page updated

Google Sites

Report abuse