Lab -2 Algorithm-Recursive Function using C programming

60-141 – Introduction to Programming II
Objectives:
– Practice designing/implementing algorithms using recursion
– Practice use of recursive functions
Pre-requisite(s):
– Read and review chapters 1-5.
In this Lab #2, you must code and document the following functions using RECURSION only.
As with the last Lab #1, test the functions by calling them from a simple interactive main() function using a menu, with different values. Overall, you should have one C program (call it Lab2.c) containing one main() function and 5 other functions listed in the table below, where the functions are called based on the user input to the menu choices. The program should contain a loop that permits users to enter a new choice of function for each loop, until exit from the loop is explicitly chosen.
1
Summation: Σ???=1=1+2+3+⋯+? ;
n > 1; reject with error message otherwise
[Note that this sum is equal to n(n+1)/2. DO NOT program the function – program the series.]
2
Factorial(0) = 1;
Factorial(n) = n * (n-1) * . . . * 2 * 1
Requirement: n >= 0; reject with error message otherwise
3
Fibonacci(0) = 0;
Fibonacci(1) = 1;
Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2);
Requirement: n >= 0; reject with error message otherwise
4
gcd (x, y) = x, if y=0
gcd (x, y) = gcd (y, x MOD y), if y > 0
Requirement: x and y both > 0; reject with error message otherwise
5
Power(a,b) = ??
Requirement: a > 0, b > 0, b is an integer; reject with error message otherwise

Answer

/*
Title: Lab #2: Algorithm, Recursive Function
Objective: Create a program with one main that solves 5 different problems using recursive method 
including Summation: (1+2+3+...+n) , factorial(n), fibonacci(n), gcd(x,y) and power(a,b) by calling a
 function using a menu.
*/

//Includes
#include <stdio.h>  //C-Preprocessor Directives

//Function Prototypes
int summationRecursive(int n); // The sum of n and all the integer numbers below it down to 0
int factorialRecursive(int n); // The product of n and all the integer numbers below it down to 1
int fibonacciRecursive(int n); // Fibonacci(n) returns the nth Fibonacci number.
int gcdRecursive(int x,int y); // The greatest common denominator of the of the two integers numbers
int powerRecursive(int a,int b); //Integer a raised to the power of integer b

//Main function
int main(void){

    int choice=0;
	//Main loop
    do{
		// Display the menu choices to the user and prompt for input.
        printf("1- Use the SUMMATION with recursive Function\n");
        printf("2- Use the FACTORIAL with recursive Function \n");
        printf("3- Use the FIBONACCI with recursive Function \n");
        printf("4- Use the GCD with recursive Function \n");
        printf("5- Use the POWER with recursive Function \n");
        printf("0- Quit\n");
        scanf("%d", &choice);

    switch(choice){
        case 1:{
			// Collect information and call summation(n) function.
            int n,result;
            printf("Please enter a value of n \n");
            scanf("%d",&n);
	          if(n<1){
		          	printf("\nError, Please enter a number greater than or equal to 1\n\n");
	            	continue;
            }
            else{
                 result=summationRecursive(n);
                 printf("\nResult is %d \n\n", result);
                 break;}
        }
        case 2:{
			// Collect information and call factorial(n) function.
            int n,result;
            printf("Please enter a value of n \n");
            scanf("%d",&n);
            if(n<0){
                  printf("\nError, Please enter a number greater than or equal to 0\n\n");
                  continue;
            }
            else{
            	     result=factorialRecursive(n);
                 printf("\nResult is %d \n\n", result);
                 break;
            }
        }
        case 3:{
			// Collect information and call fibonacci(n) function.
            int n,result;
            printf("Please enter a value of n \n");
            scanf("%d",&n);
            if(n<0){
                  printf("\nError, Please enter a number greater than or equal to 0\n\n");
                  continue;
            }
            else{
                 result=fibonacciRecursive(n);
                 printf("\nResult is %d \n\n", result);
                 break;
            }
        }
        case 4:{
			// Collect information and call gcd(x,y) function.
            int x,y,result;
            printf("Please enter a value for the first Number and then Enter a value for the Second Number \n");
            scanf("%d %d",&x,&y);
            if(x<0 || y<0){
                  printf("\nError, Please enter a number greater than or equal to 0\n\n");
                  continue;
            }
            else{
                  result=gcdRecursive(x,y);
                  printf("\nResult is %d \n\n", result);
                  break;
            }
        }
        case 5:{
			// Collect information and call power(x,y) function.
            int x,y,result;
            printf("Please enter a value for the first Number and then Enter a value for the Second Number \n");
            scanf("%d %d",&x,&y);
            if(x<0 || y<0){
                  printf("\nError, Please enter a number greater than or equal to 0\n\n");
                  continue;
            }
            else{
                  result=powerRecursive(x,y);
                  printf("\nResult is %d \n\n", result);
                  break;
            }
        }
        case 0:{
			// Display  a message for user after pressing 0 to Quit the program.
            printf("Thank you for using this program, Please come back again \n");
            break;
        }
        default:{
			// Display  a message for user after pressing a number other than 0,1,2,3,4 and 5.
            printf("Incorrect input, please choose a number between 1 and 5,or press 0 to Quit \n");
            break;
        }
    }
    }while (choice !=0); // End the while loop if the choice was 0
    return 0; //exit main
}// end of main

/*
	Objective: (Recursive)Compute the sum of n + all the numbers below it down to 1
	input: A positive integer that is 1 and higher
	output: The sum of n plus all integer numbers down to 1, example: ∑ n +(n-1) +...+ 4+ 3+ 2+ 1
*/
int summationRecursive(int n){
    // check if input is 1 or less (base case)
	if (n <= 1){
      return 1;
   }
   else{
	  // call the "summationRecursive" function
      return n + summationRecursive(n-1);
   }
}

/*
	Objective: (Recursive)Compute the factorial for integer n
	input: A positive integer that is 1 and higher (Non-negative integer)
	output: Return the factorial for integer n example: n*(n-1)*...* 4*3*2*1
*/
int factorialRecursive(int n){
   // check if input is 1 or less (base case)
   if (n <= 1){
      return 1;
   }
   else{
	  // call the "factorialRecursive" function
      return factorialRecursive(n-1) * n;
   }
}

/*
	Objective: (Recursive)Compute the nth Fibonacci number.
	input: A positive integer that is 1 and higher
	output: Compute the nth Fibonacci number which is determined by adding the last two Fibonacci numbers together,
	example: (to find the third Fibonacci number we add the two previous numbers in the sequence 0,1,1 which is 1+1=2)
*/
int fibonacciRecursive(int n)
{
	// check if input is 1 (base case)
	if (n == 1){
		return 1;
	}
	// check if input is 0 (base case)
	else if(n == 0){
		return 0;
	}
	else{
		// call the "fibonacciRecursive" function
		return fibonacciRecursive(n-1) + fibonacciRecursive(n-2);
	}
}

/*
	Objective: (Recursive)Compute the greatest common denominator of the of the two integers numbers x and y
	input: x , y are integers and y is greater than 0
	output: Return the greatest common denominator of the of the two integer numbers x,y
			such that(gcd(x,y)=gcd(y,x MOD y), if y>0 and gcd(x,y)=x, if y=0)
*/
int gcdRecursive(int x, int y){
	// check if y is 0 (base case)
	if (y == 0){
		return x;
	}
	else{
		// call the "gcdRecursive" function
		return gcdRecursive(y, x%y);
	}
}

/*
	Objective: (Recursive)Compute a raised to the power of b
	input: Two positive integer a and b
	output: return a raised to the power of b. (example for a = 3, b = 3 then power(3,3)= a*a*a = 3*3*3=27).
*/
int powerRecursive(int a, int b){
	// check if b is 1 (base case)
	if (b == 1){
		return a;
	}
	else{
		// call the "powerRecursive" function
		return a * powerRecursive(a, b-1);
	}
}