Recursion

Problem Set 7.1: Recursion (Class)

1. Printing Series

   1. Print Hello World N Times

   2. 1, 2, 3, 4, ⋯⋯⋯, N

   3. 1, 3, 5, 7, ⋯⋯⋯, 99

   4. 2, 4, 6, 8, ⋯⋯⋯, N

   5. N, N-1, N-2, …, 3, 2, 1

   6. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ⋯⋯⋯, N (Calculate the Fibonacci series up to Nth term or up to N using recursion)

2. Summation of Series

   1. 1 + 2 + 3 + 4 + ⋯⋯ + N

   2. 1 + 3 + 5 + 7 + ⋯⋯⋯ + N

   3. 2 + 4 + 6 + 8 + ⋯⋯⋯ + N

   4. 1^2 + 3^2 + 5^2 + 7^2 + ⋯⋯⋯ + (101)^2

   5. 2^3 + 4^3 + 6^3 + 8^3 + ⋯⋯⋯ + N^3

   6. N! = 1 * 2 * 3 * 4 * ⋯⋯⋯ * N

3. Array

   1. Define a recursive function that takes an integer array as an argument and prints the array elements.

   2. Define a recursive function that takes an integer array as an argument and prints the array elements in reverse order.

   3. Reverse the array

   4. Implement Linear Search using recursion

   5. Implement Binary Search using recursion

   6. Search an element (Key, Maximum, Minimum, Second Maximum, and Second Minimum) in an array using recursion

      1. Find the Key Value that exists or not in an array using recursion (Return true or false)

      2. Find the Key Value that exists or not in an array using recursion (Return the index if found otherwise return -1)

      3. Find the minimum number from an array using recursion

      4. Find the maximum number from an array using recursion

      5. Find the minimum number from an array using recursion

   7. Print Array elements in pairs of first and last elements and so on

4. Others

   1. Implement Euclidean Algorithm to Calculate Greatest Common Divisor (GCD) using recursion

   2. Least Common Multiple (LCM)

   3. Palindrome Checker

   4. Print an Integer in reverse order using recursion

   5. Print String using recursion

   6. Print String in reverse order using recursion

   7. Reverse String using recursion

   8. Tower of Hanoi

   9. Calculate a^b using recursion

   10. Calculate a^b % c using recursion

   11. Calculate sqrt(a) using recursion

   12. Base Conversion

       1. Decimal to Binary

       2. Binary to Decimal

       3. Decimal to Octal

       4. Decimal to Hexadecimal

       5. Decimal to Base N Number

       6. Octal to Decimal

       7. Hexadecimal to Decimal

       8. Base N Number to Decimal

Exercise:

fibonacci.c

#include<stdio.h>
int fib(int n);
int main(){
    int n = 6;
    for(int i=1; i<10; i++)
        printf("%d\n",fib(i));

    return 0;
}

int fib(int n){
    if(n<=2) return 1;

    return  fib(n-2) + fib(n-1);
}

bigmod.c

#include<stdio.h>
int bigmod(int a, int b, int m);
int main(){
    int a = 5, b = 15, m = 6;

    printf("%d\n", bigmod(a, b, m));

    return 0;
}

int bigmod(int a, int b, int m){
    int x;
    if(b==0){
        return 1;
    }
    if(b%2==1){
        x = bigmod(a, b-1, m);
        return (a*x) % m;
    }else{
        int x = bigmod(a, b/2, m);
        return (x*x) % m;
    }
}