a method where the solution to a problem depends on smaller ones

Image for post
Image for post
A Mandelbrot Set

Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration). Recursive algorithms have two cases: a recursive case and base case. Any function that calls itself is recursive.

Examples of recursive functions:

  1. Factorial: n! = n x (n -1) x (n-2) x … x 1
  2. Fibonacci: 1,1,2,3,5,8 ,…
  3. Multiplication (3 x 2): 3 + 3
  4. Multiplication (2 x 3): 2 + 2 + 2
  5. Summations from i = 1 to 5: 1 + 2 + 3 + 4 + 5
  6. n² + (n-1) ^2 + (n-2)² + … + 1
  7. 1 + 10 + 100 + 1000 + 10000 + …..
  8. 1 + 1 + 1 + … + 1
  9. 0 + 1 + 2 + 3 + … + n
  10. func( 0 ) = 0 , func(n) = func(n-1) + n
  11. A Mandelbrot Set

Recursion is useful for tasks that can be defined in terms of similar subtasks, for example search, sort , and traversal problems often have simple recursive solutions. At some point the function encounters a subtask that it can perform without calling itself.

  • Directly recursive: method that calls itself
  • Indirectly recursive: method that calls another method and eventually results in the original method call
  • Tail recursive method: recursive method in which the last statement executed is the recursive call
  • Infinite recursion: case where every recursive call results in another recursive call

More Articles on Recursion Algorithms

Recursion function to multiply two numbers

Multiplication can be thought of as a recursive function. Multiplication is simply adding the number ‘X’ ‘Y’ times or vice versa. For example, if I multiplied 5 by 3 (e.g. 5 * 3) the way multiplication works, we get 5 + 5 + 5 = 15 or 3 + 3 +3+ 3+ 3= 15 both are correct ways to do multiplication. This works perfectly for positive integers, but what if we wanted to multiply 5 * 0 = 0 or 0 * 5 =0 and 5 * 1 = 5 or 1 * 5 = 5, that will be our base case also known as the stopping or non-recursive case.

So, what will the recursive program look like? For the base case if input X or input Y is 0, then we will return 0, if X is 1 then we return Y, if Y is 1 then we return X. Both X and Y are our input parameter variables. The multiplication function is below to multiply two positive numbers recursively. Note: you cannot use this function for negative values.

int Multiply(int X, int Y){
if( X == 0 || Y== 0)
return 0;
if(X == 1)
return Y;
if(Y == 1)
return X;
return Y + Multiply(X -1, Y);
}

Popular recursive puzzle Towers of Hanoi

The Tower of Hanoi is a game or puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape. The objective of the puzzle is to move the entire stack to another rod, obeying specific rules.

Tower of Hanoi recursive program (Javascript)

/*
*This is a Tower of hanoi recursive program
* written in javascript
*/
function Hanoi(n, from, to , via)
{
if (n==0) return;

Hanoi(n-1, from, via , to);

moveDisk(from,to);

Hanoi(n-1, via, to , from);
}

If you want to read up on more recursion problems or Discrete Math topics in general a great book to easily learn and practice these topics is Practice Problems in Discrete Mathematics by Bojana Obrenic’, and Discrete Math Workbook: Interactive Exercises by James R. bush.

Image for post
Image for post
Practice Problems in Discrete Mathematics by Bojana Obrenic’
Image for post
Image for post
Discrete Math Workbook: Interactive Exercises by James R. bush

Thanks for reading this article I hope its helpful to you all ! Keep up the learning, and if you would like more computer science, programming and algorithm analysis videos please visit and subscribe to my YouTube channels (randerson112358 & compsci112358 )

Check Out the following for content / videos on Computer Science, Algorithm Analysis, Programming and Logic:

YouTube Channel:
randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

compsci112358:
https://www.youtube.com/channel/UCbmb5IoBtHZTpYZCDBOC1CA

Website:
http://everythingcomputerscience.com/

Video Tutorials on Recurrence Relation:
https://www.udemy.com/recurrence-relation-made-easy/

Video Tutorial on Algorithm Analysis:
https://www.udemy.com/algorithm-analysis/

Twitter:
https://twitter.com/CsEverything

YouTube Channel:

Image for post
Image for post

Computer Science Website:

Image for post
Image for post

Udemy Videos on Algortithm Analysis:

Image for post
Image for post

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store