Discrete Mathematics

Recursion

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).

Overview:

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 itseld 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^2 + (n-1) ^2 + (n-2)^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

Recursive definition

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

Factorial Numbers

Factorial numbers defined recursively example:
factorial(0) = 1;
factorial(n) = n * factorial(n-1);

Examples

0! = 1
1! = 1 * 1 = 1
2! = 2 * 1 * 1 = 2
3! = 3 * 2 * 1 * 1 = 6
4! = 4 * 3 * 2 * 1 * 1 = 24

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.


Solution Java Program

Tower of Hanoi recursive program (Javascript)

/*
*This is a Tower of hanoi recursive program
* written in javascript
*This program will tell you the correct
* moves to make for any number of disks 'n'
* in this case n = 4
*/

function move(n, a, b, c) {
if (n > 0) {
move(n-1, a, c, b);
console.log("Move disk from " + a + " to " + c);
move(n-1, b, a, c);
}
}
move(4, "A", "B", "C");

Recursive function to recurrence relation

randerson112358

Learn how to change a recursive function into a recurrence relation

Download PDF

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 the 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 ? Base case if input X or input Y is 0 we will return 0, if X is 1 then we return Y , if Y is 1then we return X. Both X and Y are our input parameter variables. You look at the multiplication function next to this paragraph to see how we would 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;

returnY + Multiply(X -1, Y);
}

Recursive Power Function C program

computer science (compsci112358)

In this video I show how to write a recursive power function in C programming.

â–ºSupport this channel for FREE by doing your Amazon shopping through this link (bookmark it!): https://www.amazon.com/?tag=everythingc06-20

Get the code here:
https://github.com/randerson112358/C-Programs/blob/master/power_function_recursion.c

Download PDF

Recursion function to multiply 2 numbers

randerson112358

Learn how to use recursion to multiply two numbers

Download PDF

Code: Fibonocci Recursion

/* C Program for a recursive fibonacci function */
 #include< stdio.h >
 
int Fibonacci(int);
 
main()
{
   int n, i = 0, c;
 
   scanf("%d",&n);
 
   printf("Fibonacci series\n");
 
   for ( c = 1 ; c <= n ; c++ )
   {
      printf("%d\n", Fibonacci(i));
      i++; 
   }
 
   return 0;
}
 
int Fibonacci(int n)
{
   if ( n == 0 )
      return 0;
   else if ( n == 1 )
      return 1;
   else
      return ( Fibonacci(n-1) + Fibonacci(n-2) );
}