Recursion Examples

For 3502C

Simple recursion

void fun(int a){
    if(a==0)
        return; 
    fun(a-1);
}

More complex, but practical example of recursion

void fun1(int a){// this will print from 5-1, calling itself after it printed
    if(a==0)
        return;
    printf("%d ", a); // it won't print after 0; 
fun(a-1);

}
void fun2(int a){ // this calls first until fun(0);
    if(a==0)// condition to make sure this doesn't run infinitly 
        return;
    fun(a-1);// THIS calls until fun(0);
    printf("%d ", a);// after it is done, it will return to the previous function call, printing from (1 to 5)
}

main(){
    int a =5;
    fun1(a);
    fun2(a);
}

How to add using recursion?

int sum_rec(int a){
    
    if(a == 1) return 1; // the base case that is the condition, and once it calls 1, it will return 1, and contiously add over and over again
return a + sum_rec(a-1);// this will add continously, but before it returns, it will keep calling itself over and over until the condition is met. 


}

How to figure out a factorial using recursion?(Factorial)

#include <stdio.h>
int factorial(int n);
int main()
{
int n;
printf("Enter n: ");
scanf("%d", &n);
printf("%d! = %d\n", n, factorial(n));
return 0;
}

/* MAIN THING TO UNDERSTAND*/
int factorial(int n)
{
if(n == 0)
return 1;
return n * factorial(n-1);

How to print repeatably using recursion?

// 

tip_rate = 0.15; 

void chart(int min, int max){
    if(min <= max) {
        printf("$%d    $%f\n", min, min*tip_rate);

     chart(min +1, max);
    }

}

How to do Fibonacci numbers using recursion?

#include <stdio.h>
int fibonacci(int n);
int main()
{
int n;
printf("Enter n: ");
scanf("%d", &n);
printf("%d-th fibonacci number is = %d\n", n, fibonacci(n));
return 0;
}

/* MAIN THING TO UNDERSTAND*/
int fibonacci(int n)
{
if(n < 2)
return n;
return fibonacci(n-1) + fibonacci(n-2);
}

How to do power with recursion?(solving exponents)

#include <stdio.h>
int power(int x, int y);
int main()
{
int x, y;
printf("Enter x: ");
scanf("%d", &x);
printf("Enter y: ");
scanf("%d", &y);
printf("%d^%d = %d\n", x, y, power(x, y));
return 0;
}

/* MAIN THING TO UNDERSTAND*/
int power(int x, int y)
{
if(y == 0)
return 1;
return x * power(x, y-1);

How to do the fast_exp(power rule”) method checking odd and even numbers?

int fast_exp(int b, int p)
{

if (p==0)
    return 1;

int r = fast_exp(b, p/2)
if(p%2 == 0) // if the power is even
    return r * r;
else // if the power is odd
    return r * r * b; // multiplying by base as well to account for odd


    


}

How to do Tower of Hanoi?(changing from “from_rod” to “to_rod” using 1 auxiliary rod?

// think of this kinda like a swap function, going from i = temp
// i = j, and j = temp, but instead, aux_rod is temp
void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod)
{
if (n == 1)// if this is disk 1
{
printf("\n Move disk 1 from rod %c to rod %c", from_rod, to_rod);
return;
}
towerOfHanoi(n-1, from_rod, aux_rod, to_rod);// moving from from_rod to aux_rod, using to_rod as an auxiliary rod

printf("\n Move disk %d from rod %c to rod %c", n, from_rod, to_rod);
towerOfHanoi(n-1, aux_rod, to_rod, from_rod);// sending from auxiliary to to_rod, 
}


int main()
{
int n = 4; // Number of disks
towerOfHanoi(n, 'A', 'C', 'B'); // A, B and C are names of rods
return 0;
}

How to do recursive permutations?

void RecursivePermute(char str[], int k) { // with char string
int j;
// Base-case: Since all letters are fixed, we can ONLY print what's stored in str.
if (k == strlen(str))
printf("%s\n", str); // prints up a combination when k = 4(example string length)
else {
// Loop through each possible starting letter for index k, the first index for which we have a choice.// surprized that there is a for loop with recursion. 
for (j=k; j<strlen(str); j++) {

// Place the character stored in index j in location k.
ExchangeCharacters(str, k, j);

// Print out all of the permutations with that character just chosen above fixed.
RecursivePermute(str, k+1);

// Put the original character that used to be there back in its place.
ExchangeCharacters(str, j, k);
        }

    }

}

How do to 2D permutations with helper/no helper arrays

How to reverse print using recursion?

#include <stdio.h>
#include <string.h>
#define SIZE 50
void reverseprint(char word[], int len);
int main()
{
char word[SIZE];
printf("Enter word: ");
scanf("%s", word);
printf("In reverse order: \n");
reverseprint(word, strlen(word));
printf("\n");
return 0;
}

/* MAIN THING TO UNDERSTAND*/
void reverseprint(char word[], int len)
{
printf("%c", word[len-1]);
if (len > 0)
reverseprint(word, len-1);
}

How to do binary search with recursion?

#include <stdio.h>
// A recursive implementation of the Binary Search Algorithm.
// Return index of the item, if found, otherwise return -1
int binarySearch(int arr[], int low, int high, int x) {
if (low > high) // element not found and we crossed the limit
return -1;
int mid = (low + high)/2 ; //integer division, odd or even number of items are
handled here
// Found at mid, return index
if (arr[mid] == x)
return mid;
// item smaller than the one in mid, look in the left subarray
else if(arr[mid] > x)
return binarySearch(arr, low, mid - 1, x);
//item larger than the one in mid, look in the right subarray
else
return binarySearch(arr, mid + 1, high, x);
}
int main()
{
int arr[] = {1, 2, 4, 5, 7, 9, 10, 13};
int n = 8;
int x = 10; //item that we will be looking for
int result = binarySearch(arr, 0, n - 1, x);
if (result == -1)
printf("Not found\n");
else
printf("%d found at index %d\n", x, result);
return 0;

How to do bubbleSearch with recursion?

#include <stdio.h>
// swap i-th element with j-th one
void swap(int* arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// Last i elements are already in place, so the loop
// will only num n - i - 1 times
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1])
swap(arr, j, j + 1);
}
}
}
int main() {
int arr[] = {7, 9, 2, 5, 6};
int n = 5;
// Calling bubble sort on array arr
bubbleSort(arr, n);
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;

How to do FloodFill?

#include <stdio.h>
#define SIZE 10
// print the contents in the grid
void display_grid(char grid[][SIZE], int r, int c)
{
for(int i=0; i<r; i++)
{
for(int j=0; j<c; j++)
{
printf("%c", grid[i][j]);
}
printf("\n");
}
}

/* MAIN THING TO UNDERSTAND*/
// recursive function
void flood_fill_rec(char grid[][SIZE], int x, int y, char new_ch, char old_ch)
{
if(x<0 || y<0 || x>=SIZE || y >=SIZE) //if it is out of the matrix
return;
if(grid[x][y] != old_ch) //if it is not the old char, no need to go to other
//direction for that cell
return;
grid[x][y] = new_ch;
flood_fill_rec(grid, x+1, y, new_ch, old_ch);
flood_fill_rec(grid, x-1, y, new_ch, old_ch);
flood_fill_rec(grid, x, y+1, new_ch, old_ch);
flood_fill_rec(grid, x, y-1, new_ch, old_ch);
}
// Second main thing to understand!
// wrapper function
void flood_fill(char grid[][SIZE], int x, int y, char ch)
{
char old_char = grid[x][y];
flood_fill_rec(grid, x, y, ch, old_char);
}


int main(void) {
char grid[SIZE][SIZE] = {
{'*', '*','*','*','*','*','*','*','*','*'},
{'*', '*',' ' , ' ', '*', '*', '*',' ', ' ', '*'},
{'*', ' ',' ' , ' ', '*', '*', ' ',' ', ' ', '*'},
{'*', ' ',' ' , ' ', ' ', '*', ' ',' ', ' ', '*'},
{'*', ' ',' ' , ' ', ' ', '*', ' ',' ', ' ', '*'},
{'*', ' ',' ' , ' ', ' ', ' ', ' ',' ', ' ', '*'},
{'*', ' ',' ' , ' ', ' ', ' ', ' ',' ', ' ', '*'},
{'*', ' ',' ' , ' ', ' ', '*', ' ',' ', ' ', '*'},
{'*', ' ',' ' , ' ', ' ', '*', ' ',' ', ' ', '*'},
{'*', '*','*','*','*','*','*','*','*','*'}
};
printf("Before: \n");