Lets write a C program to find GCD(Greatest Common Divisor) or HCF(Highest Common Factor) of two positive integer numbers input by the user using Euclid’s Algorithm and by using Recursive function call logic.
If user inputs 2 numbers n1 and n2, reduce the bigger number by modulo dividing it by the smaller number. For example, if n1 is greater than n2, then reduce the value of n1 by replacing it with n1%n2.
Assume that we’ve a function gcd() which returns gcd of 2 numbers passed to it. Ex: gcd(n1, n2);
According to Euclid’s Algorithm, we’ll get the same gcd if we reduce the bigger number by modulo dividing it by smaller number.
If n1 > n2 we need to pass gcd(n1%n2, n2); If n2 > n1, we need to pass gcd(n1, n2%n1);
We need to recursively execute above 2 lines of logic until either n1 is 0 or until n2 is 0. If n1 is 0, then value present in n2 is the gcd of (n1,n2). If n2 is 0, then value present in n1 is the gcd of (n1,n2).
Video Tutorial: C Program To Find GCD of Two Numbers using Recursion: Euclid’s Algorithm
printf("Enter a positive number to find its Factorial\n");
scanf("%d", &num);
printf("\nFactorial of %d is %d.\n", num, fact(num));
return 0;
}
int fact(int num)
{
if(num)
return(num * fact(num - 1));
else
return 1;
}
#include<stdio.h>
int fact(int);
int main()
{
int num;
printf("Enter a positive number to find its Factorial\n");
scanf("%d", &num);
printf("\nFactorial of %d is %d.\n", num, fact(num));
return 0;
}
int fact(int num)
{
if(num)
return(num * fact(num - 1));
else
return 1;
}
Output 1: Enter a positive number to find its Factorial 7
Factorial of 7 is 5040.
Output 2: Enter a positive number to find its Factorial 8
Factorial of 8 is 40320.
Logic To Find Factorial of a Number using Recursion
We ask the user to enter a positive integer number and we pass this number to a function called fact().
Inside fact() function Inside fact() function, we check if the number is non-zero, if true, we execute the code inside if block orelse(if num is zero), then the code inside else block gets executed.
Inside if block, we add the factorial of (num-1) to the value of num.
num * fact(num – 1)
and return the result to the calling function.
Inside else block, we simply return 1. Because factorial of 0 is 1. So when num is 0, we return 1.
Example:
num
num * fact(num-1)
5
5 * fact(4)
4
4 * fact(3)
3
3 * fact(2)
2
2 * fact(1)
1
1 * fact(0)
Value Returning – Control Shifting back.
Function
Return Value
Result
1 * fact(0)
return 1;
1 * 1 = 1
2 * fact(1)
1
2 * 1 = 2
3 * fact(2)
2
3 * 2 = 6
4 * fact(3)
6
4 * 6 = 24
5 * fact(4)
24
5 * 24 = 120
Finally 120 will be returned to main() method where we call the fact() method.
Source Code: C Program To Find Factorial of a Number using Recursion and Ternary or Conditional Operator
printf("Enter a positive number to find its Factorial\n");
scanf("%d", &num);
printf("\nFactorial of %d is %d.\n", num, fact(num));
return 0;
}
int fact(int num)
{
return( (num > 0) ? (num * fact(num - 1)) : 1 );
}
#include<stdio.h>
int fact(int);
int main()
{
int num;
printf("Enter a positive number to find its Factorial\n");
scanf("%d", &num);
printf("\nFactorial of %d is %d.\n", num, fact(num));
return 0;
}
int fact(int num)
{
return( (num > 0) ? (num * fact(num - 1)) : 1 );
}
Output 1: Enter a positive number to find its Factorial 5
Factorial of 5 is 120.
Output 2: Enter a positive number to find its Factorial 6
Whenever there is a recursive function call, function instance and the memory associated with that function instance gets pushed into the stack. When any function instance returns a value, that function instance and memory associated with that function instance gets popped out or removed or gets deleted from the memory stack.
#include<stdio.h>
#include<math.h>
int reverse(int num)
{
if(num)
return( (num%10) * pow(10, (int)log10(num)) + reverse(num/10) );
else
return 0;
}
int main()
{
int num, isNegative = 1, result = 0;
printf("Enter a number to reverse\n");
scanf("%d", &num);
isNegative = (num < 0);
if(isNegative)
num *= -1;
result = reverse(num);
if(isNegative)
result *= -1;
printf("Reverse of %d is %d\n", num, result);
return 0;
}
Output 1: Enter a number to reverse 12345 Reverse of 12345 is 54321
Output 2: Enter a number to reverse -12345 Reverse of -12345 is -54321
Logic To Reverse a Number using Recursion
We ask the user to input a number, and store it inside variable num. If num is negative, then we store 1(true) inside variable isNegative or store 0(false) inside variable isNegative if num is positive.
If isNegative is 1, then we change the value of num to positive and send it as argument to reverse() function.
Inside reverse() function If num is 0, it returns 0. Else we recursively call reverse() function as follows:
num % 10 gives the last digit in the number. log10(num) gives the length of the number or the number of digits present in the number. The count starts from 0. Ex: if num = 12345, then log10(num) would give 4.
num/10 reduces the number by 1 digit from right.
pow(10, (int)log10(num)) is used to properly place the reminder value in its decimal place.
Lets assume that user has input 1234 as value of num.
i.e., num = 1234;
Recursive Function Calls – Stacking of calls
num
num % 10
num%10*log10(num)
num/10
1234
reverse(1234)
1234
4
4 * 103 = 4000
reverse(123)
123
3
3 * 102 = 300
reverse(12)
12
2
2 * 101 = 20
reverse(1)
1
1
1 * 100 = 1
reverse(0)
Value Returning – Control Shifting back.
Return To
result
resolve
Return Value
reverse(0)
0
reverse(1)
1* 100+reverse(0)
1 * 1 + 0
1
reverse(12)
2*101+reverse(1)
2 * 10 + 1
21
reverse(123)
3*102+reverse(12)
3 * 100 + 21
321
reverse(1234)
4*103+reverse(123)
4 * 1000 + 321
4321
Note: Whenever there is a call to a function, the function instance(and memory associated with it) gets stored in the memory stack. Once the function returns value to calling function, the control shifts back to the calling function and the memory instance gets popped or deleted out of the memory stack immediately after returning the value.
Source Code: C Program To Reverse a Number using Recursion and Ternary Operator
printf("Reverse of %d is %d\n", num, reverse(num, count));
return 0;
}
#include<stdio.h>
#include<math.h>
int reverse(int num, int len)
{
if(num)
return( (num%10) * pow(10, len-1) + reverse(num/10, len-1) );
else
return 0;
}
int main()
{
int num, count = 0, temp;
printf("Enter a number to reverse\n");
scanf("%d", &num);
temp = num;
while(temp)
{
count++;
temp = temp / 10;
}
printf("Reverse of %d is %d\n", num, reverse(num, count));
return 0;
}
Output 1: Enter a number to reverse 123456 Reverse of 123456 is 654321
Output 2: Enter a number to reverse -123456 Reverse of -123456 is -654321
Logic To Reverse a Number using Recursion without using log10() function
Inside main method itself we calculate the number of digits present in the user entered number and then pass that information to the function reverse() along with the user entered number.
reverse(num, count);
Inside reverse() function Inside reverse() function, we get the reminder by modulo dividing num by 10. We place this remainder in it’s decimal place by multiplying it with
pow(10, len-1)
where len is the length or the number of digits present in the number.
Next we recursively call reverse() function and pass the value of (num/10) and (len-1).
Finally we combine all these results using below formula and return the value to the calling function recursively, until num is equal to 0:
Write a recursive function to obtain the first 25 numbers of a Fibonacci sequence. In a Fibonacci sequence the sum of two successive terms gives the third term. Following are the first few terms of the Fibonacci sequence:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 …
Note: In this video tutorial we’ve taken 0 and 1 as the first 2 numbers in the Fibonacci series- they’re called Seed Values. And we ask the user to enter the limit or the number of terms to be printed in the Fibonacci Series.
At the end of this article you can find C program source code which exactly matches the above problem statement. So if you’re only looking for exact solution to above problem statement, then directly scroll down to the end of this article and you can get the source code for it.
Fibonacci Series is a series of numbers where the first two Fibonacci numbers are 0 and 1, and each subsequent number is the sum of the previous two. Its recurrence relation is given by Fn = Fn-1 + Fn-2.
Below we have series of Fibonacci numbers(10 terms): 0 1 1 2 3 5 8 13 21 34
How Its Formed: 0 <– First Number (n1) 1 <– Second Number (n2) 1 <– = 1 + 0 (1 and 0 are previous 2 terms) 2 <– = 1 + 1 3 <– = 2 + 1 5 <– = 3 + 2 8 <– = 5 + 3 13 <– = 8 + 5 21 <– = 13 + 8 34 <– = 21 + 13
Video Tutorial: Generating Fibonacci Series using Recursion: C Program
printf("Enter no of terms of Fibonacci Series to be printed\n");
scanf("%d", &limit);
for(count = 1; count <= limit; count++)
{
printf("\n%d. %d\n", count, fib(count));
}
return 0;
}
int fib(int num)
{
if(num == 1)
return(0);
elseif(num == 2 || num == 3)
return(1);
else
return( fib(num-1) + fib(num-2) );
}
#include<stdio.h>
int fib(int);
int main()
{
int limit, count;
printf("Enter no of terms of Fibonacci Series to be printed\n");
scanf("%d", &limit);
for(count = 1; count <= limit; count++)
{
printf("\n%d. %d\n", count, fib(count));
}
return 0;
}
int fib(int num)
{
if(num == 1)
return(0);
else if(num == 2 || num == 3)
return(1);
else
return( fib(num-1) + fib(num-2) );
}
Output: Enter no of terms of Fibonacci Series to be printed 8
1. 0
2. 1
3. 1
4. 2
5. 3
6. 5
7. 8
8. 13
Logic To Generate Fibonacci Series using For Loop
We ask the user to enter the limit or the number of terms he or she wants to print or display in the Fibonacci series. We store the user input number in a variable called limit.
We initialize the loop counter variable count to 1. Now we iterate the for loop from 1 to user input limit times. For each iteration we call the function fib() and pass the value present in the variable count. fib(count) gets the Fibonacci number for the count or nth term.
Inside fib() function We know the first two terms in the Fibonacci series which are 0 and 1. To get the third term in this series we add 0 and 1. So the next term is 0+1 which is 1 once again. We’ll write separate conditions for this inside the fib() function.
If num is 1, we return 0. Which is the first term in the series. If num is 2 or 3, we return 1. Because 1 is the third as well as forth term in the series. If num is neither 1, nor 2 or 3, then we call the same function( fib() ) and pass the immediate preview 2 terms of the Fibonacci Series which are (num – 1) and (num -2), and add it to get the next term in the series.
fib(num-1) + fib(num-2)
This equation will keep calling itself and ultimately reduce to fib(1) or fib(2) or fib(3) for which we already know the values.
Example:
If user inputs a value of 5 to limit, then we need to print 5 terms in the Fibonacci Series. We write a for loop and iterate the loop from 1 to limit times. For each iteration of the for loop, loop counter value increments by 1. Inside for loop we call fin() method and pass the value present inside loop counter variable count. Through out the life cycle of the for loop, count will have value from 1 to 5. i.e., 1, 2, 3, 4, 5
For each iteration following code will be executed, and the returned value is printed out to the console window.
num or count
fib()
Output
1
fib(1)
0
2
fib(2)
1
3
fib(3)
1
4
fib(4) = fib(3) + fib(2)
2
5
fib(5) = fib(4) + fib(3)
3
For fifth iteration fib(5) = fib(4) + fib(3) which follows the recurrence relation formula F(n) = F(n-1) + F(n-2).
Here fib(4) can be reduced to: fib(4) = fib(4-1) + fib(4-2) fib(4) = fib(3) + fib(2)
Now replace the value of fib(4) in below equation:
#include<stdio.h>
int fib(int);
int main()
{
int limit = 25, count;
for(count = 1; count <= limit; count++)
{
printf("\n%d. %d\n", count, fib(count));
}
return 0;
}
int fib(int num)
{
return( (num == 1 || num == 2) ? 1 : ( fib(num-1) + fib(num-2) ) );
}
Output: We get the same 25 terms in Fibonacci series as with above source code. Know more about ternary operator or conditional operator in a separate video tutorial: Ternary Operator / Conditional Operator In C
Disadvantages of using Recursion
Recursive Calls are not always efficient. Particularly in calculating Fibonacci Series – It’s better to use the regular iterative ways, instead of recursion. Recursion in this program creates lot of overhead for memory stack.
printf("Biggest of %d, %d and %d is %d\n", a, b, c, biggest(a, b, c));
return 0;
}
// function definition
int biggest(int x, int y, int z)
{
if(x > y && x > z)
{
return x;
}
else
{
if(y > z)
return y;
else
return z;
}
}
#include<stdio.h>
int biggest(int, int, int); // function prototype
int main()
{
int a, b, c;
printf("Enter 3 integer numbers\n");
scanf("%d%d%d", &a, &b, &c);
//function call biggest(a, b, c)
printf("Biggest of %d, %d and %d is %d\n", a, b, c, biggest(a, b, c));
return 0;
}
// function definition
int biggest(int x, int y, int z)
{
if(x > y && x > z)
{
return x;
}
else
{
if(y > z)
return y;
else
return z;
}
}
Output Enter 3 integer numbers 50 40 60 Biggest of 50, 40 and 60 is 60
Source Code: C Program To Find Biggest of Three Numbers using Function, Using Ternary Operator
printf("Biggest of %d, %d and %d is %d\n", a, b, c, biggest(a, b, c));
return 0;
}
// function definition
int biggest(int x, int y, int z)
{
return( (x>y && x>z)?x:(y>z)?y:z );
}
#include<stdio.h>
int biggest(int, int, int); // function prototype
int main()
{
int a, b, c;
printf("Enter 3 integer numbers\n");
scanf("%d%d%d", &a, &b, &c);
//function call biggest(a, b, c)
printf("Biggest of %d, %d and %d is %d\n", a, b, c, biggest(a, b, c));
return 0;
}
// function definition
int biggest(int x, int y, int z)
{
return( (x>y && x>z)?x:(y>z)?y:z );
}
Logic To Find Biggest of 3 Numbers using Function
We ask the user to enter 3 integer numbers. We pass those 3 integer numbers to user defined function biggest. Inside function biggest we use ternary operator to determine the biggest of those 3 numbers. Function biggest returns the biggest of the 3 numbers back to the calling method/function – in above progam its main() method.
Note: Function biggest returns integer type data. And it takes 3 arguments of type integer. We’re calling function biggest from inside printf() function.