Lets write a C program to count the number of occurrences of digit k in user input positive integer number n, using iterative logic. We will be using while loop to iterate in this program.
For Example:
If user inputs n = 1550, and k = 5, then our C program should find how many times digit 5 is present in number 1550.
Note: (num % 10) fetches last digit in num. If num = 1234; (num%10) fetches the last digit from right, which is 4.
(num/10) removes the last number from right. If num = 1234; (num/10) removes last digit i.e., 4 and the result of (num/10) will be 123.
Source Code: C Program To Count Digit k in Number n
#include<stdio.h>
int occurrence(int, int);
int main()
{
int n, k;
printf("Enter a positive integer number\n");
scanf("%d", &n);
printf("Which digits occurrence you want to check for?\n");
scanf("%d", &k);
printf("\n%d has appeared %d times in %d.\n", k, occurrence(n, k), n);
return 0;
}
int occurrence(int num, int k)
{
int count = 0;
while(num)
{
if(num%10 == k)
count++;
num = num / 10;
}
return count;
}
Output: Enter a positive integer number 1550 Which digits occurrence you want to check for? 5
5 has appeared 2 times in 1550.
Logic To Count Digit k in Number n
We ask the user to input values for variable n and k. We need to find the number of occurrences of digit k in number n. We pass both these variables to a function called occurrence().
Inside occurrence() function Inside occurrence() function, we keep iterating the while loop until num value is 0. Btw, n value is copied into variable num. Now we check if (num%10) is equal to value of k. (num%10) fetches the last digit in the num. If (num%10) is equal to k, then we increment the value of count by 1. For each iteration of while loop we decrement the value of num by 1 digit, from right, by dividing num by 10 i.e., (num/10).
Once num is 0, control exits while loop and value of count will be returned to main method.
If num%10 is not equal to k, then we simply divide the num by 10, and reduce the value of num by one digit from right.
Source Code: C Program To Count Digit k in Number n using Recursion
#include<stdio.h>
int occurrence(int, int);
int main()
{
int n, k;
printf("Enter a positive integer number\n");
scanf("%d", &n);
printf("Which digits occurrence you want to check for?\n");
scanf("%d", &k);
printf("\n%d has appeared %d times in %d.\n", k, occurrence(n, k), n);
return 0;
}
int occurrence(int num, int k)
{
if(num == 0)
return 0;
else if(k == (num%10))
return(1 + occurrence(num/10, k));
else
return(occurrence(num/10, k));
}
Output: Enter a positive integer number 12555 Which digits occurrence you want to check for? 5
5 has appeared 3 times in 12555.
Source Code: C Program To Count Digit k in Number n using Recursion and Ternary or Conditional Operator
#include<stdio.h>
int occurrence(int, int);
int main()
{
int n, k;
printf("Enter a positive integer number\n");
scanf("%d", &n);
printf("Which digits occurrence you want to check for?\n");
scanf("%d", &k);
printf("\n%d has appeared %d times in %d.\n", k, occurrence(n, k), n);
return 0;
}
int occurrence(int num, int k)
{
return( (num == 0)? 0 :
(k == (num%10)) ?
(1 + occurrence(num/10, k)) :
(occurrence(num/10, k)));
}
Output: Enter a positive integer number 155555061 Which digits occurrence you want to check for? 5
Logic To Count Digit k in Number n using Recursion
First we write the base condition i.e., if num is 0, then our function returns 0 to the calling function. Else if num%10 is equal to the value of k, then we return (1 + occurrence(num/10, k)). That way we count or increment by 1 for each time we found a digit which is equal to k, and then we reduce the num by one digit from right by doing num/10. k value will remain same throughout the program execution.
If num%10 is not equal to k, then we simply divide the num by 10, and reduce the value of num by one digit from right.
Example:
Lets assume that user input value for n and k: n = 1223; k = 2;
Source Code: C Program To Find Sum of Squares of Digits using Recursion
#include<stdio.h>
int square(int num)
{
if(num == 0)
return 0;
else
return( (num%10) * (num%10) + square(num/10) );
}
int main()
{
int num;
printf("Enter a positive integer number:\n");
scanf("%d", &num);
printf("Sum of squares of digits of %d is %d.\n", num, square(num));
return 0;
}
Output: Enter a positive integer number: 123 Sum of squares of digits of 123 is 14.
Source Code: C Program To Find Sum of Squares of Digits using Recursion and pow() method
#include<stdio.h>
#include<math.h>
int square(int num)
{
if(num == 0)
return 0;
else
return( pow((num%10), 2) + square(num/10) );
}
int main()
{
int num;
printf("Enter a positive integer number:\n");
scanf("%d", &num);
printf("Sum of squares of digits of %d is %d.\n", num, square(num));
return 0;
}
Output: Enter a positive integer number: 123 Sum of squares of digits of 123 is 14.
Here we are making use of pow() method present inside math.h library file. pow() takes base value as first argument and exponent value as its second argument.
Source Code: C Program To Find Sum of Squares of Digits using Recursion, Ternary/Conditional Operator and pow() method
#include<stdio.h>
#include<math.h>
int square(int);
int main()
{
int num;
printf("Enter a positive integer number:\n");
scanf("%d", &num);
printf("Sum of squares of digits of %d is %d.\n", num, square(num));
return 0;
}
int square(int num)
{
return( (num == 0) ? 0 : ( pow((num % 10), 2) + square(num/10) ));
}
Output 1: Enter a positive integer number: 123 Sum of squares of digits of 123 is 14.
Output 2: Enter a positive integer number: 2103 Sum of squares of digits of 2103 is 14.
Output 3: Enter a positive integer number: 456 Sum of squares of digits of 456 is 77.
Output 4: Enter a positive integer number: 2020 Sum of squares of digits of 2020 is 8.
Output 5: Enter a positive integer number: 2021 Sum of squares of digits of 2021 is 9.
Source Code: C Program To Convert Decimal To Binary Number using Recursion
#include<stdio.h>
int binary_rec(int);
int binary(int);
int main()
{
int num;
printf("Enter a Decimal number\n");
scanf("%d", &num);
printf("Binary Equivalent (Iterative) of %d is %d\n", num, binary(num));
printf("Binary Equivalent (Recursive) of %d is %d\n", num, binary_rec(num));
return 0;
}
int binary_rec(int num)
{
if(num == 0)
return 0;
else
return((num % 2) + 10 * binary_rec(num/2));
}
int binary(int num)
{
int rem, bin = 0, place = 1;
while(num)
{
rem = num % 2;
num = num / 2;
bin = bin + (rem * place);
place = place * 10;
}
return(bin);
}
Output 1: Enter a Decimal number 14
Iterative Logic Binary Equivalent of 14 is 1110
Recursive Logic Binary Equivalent of 14 is 1110
Output 2: Enter a Decimal number 41
Iterative Logic Binary Equivalent of 41 is 101001
Recursive Logic Binary Equivalent of 41 is 101001
Logic To Convert Decimal Number To Binary Number using Recursion
Recursive Function Logic Assume that user inputs num value as 14.
num
num % 2
(num % 2) + 10 * binary_rec(num/2)
14
14 % 2
(0) + 10 * binary_rec(7)
7
7 % 2
(1) + 10 * binary_rec(3)
3
3 % 2
(1) + 10 * binary_rec(1)
1
1 % 2
(1) + 10 * binary_rec(0)
Value Returning – Control Shifting back.
Return Value
To
Result
return 0;
(1) + 10 * binary_rec(0)
(1) + 10 * 0 = 1
1
(1) + 10 * binary_rec(1)
(1) + 10 * 1 = 11
11
(1) + 10 * binary_rec(3)
(1) + 10 * 11 = 111
111
(0) + 10 * binary_rec(7)
(0) + 10 * 111 = 1110
Binary Equivalent of Decimal Number 14 is 1110.
Source Code: C Program To Convert Decimal To Binary Number using Recursion and Ternary or Conditional Operator
#include<stdio.h>
int binary_rec(int);
int binary(int);
int main()
{
int num;
printf("Enter a Decimal number\n");
scanf("%d", &num);
printf("\nIterative Logic\n");
printf("Binary Equivalent of %d is %d\n\n", num, binary(num));
printf("\nRecursive Logic\n");
printf("Binary Equivalent of %d is %d\n\n", num, binary_rec(num));
return 0;
}
int binary_rec(int num)
{
return( (num == 0) ? 0 : (num % 2) + 10 * binary_rec(num / 2));
}
int binary(int num)
{
int rem, bin = 0, place = 1;
while(num != 0)
{
rem = num % 2;
num = num / 2;
bin = bin + (rem * place);
place = place * 10;
}
return(bin);
}
Source Code: C Program To Convert Decimal To Binary Number using Recursion
Another Method
#include<stdio.h>
void binary_rec(int);
int binary(int);
int main()
{
int num;
printf("Enter a Decimal number\n");
scanf("%d", &num);
printf("\nIterative Logic\n");
printf("Binary Equivalent of %d is %d\n\n", num, binary(num));
printf("\nRecursive Logic\n");
printf("Binary Equivalent of %d is ", num);
binary_rec(num);
printf("\n");
return 0;
}
void binary_rec(int num)
{
if(num == 1)
printf("1");
else
{
binary_rec(num/2);
printf("%d", num%2);
}
}
int binary(int num)
{
int rem, bin = 0, place = 1;
while(num != 0)
{
rem = num % 2;
num = num / 2;
bin = bin + (rem * place);
place = place * 10;
}
return(bin);
}
Output: Enter a Decimal number 14
Iterative Logic Binary Equivalent of 14 is 1110
Recursive Logic Binary Equivalent of 14 is 1110
Here we simply divide the number by 2 and keep passing it as new value of num to binary_rec() function, and we print num%2 once num = 1 and it returns the value 1.
Number Systems
1. Binary Number System uses base 2 and digits 01. 2. Octal Number System uses base 8 and digits 01234567. 3. Decimal Number System uses base 10 and digits 0123456789. 4. Hexadecimal Number System uses base 16 and digits 0123456789ABCDEF.
A positive integer is entered through the keyboard, write a C program to obtain the prime factors of the number. Modify the function suitably to obtain the prime factors recursively.
Analyze The Problem Statement
According to problem statement we need to find prime factors of user input positive integer number using iterative logic first, and then modify it and write a recursive logic to obtain the same result.
In our video tutorial we’ll write both iterative as well as recursive logic. This way you can compare the two – both the similarities and differences in the code.
For Example: Prime factors of 24 are 2, 2, 2 and 3.
Note: Both 24 and 35 are not prime numbers, but the factors(2, 3, 5 and 7) we display are prime numbers and multiplying all the prime factors should give the original number.
Video Tutorial: C Program To Find Prime Factors of a Number using Recursion
Source Code: C Program To Find Prime Factors of a Number using Recursion
#include<stdio.h>
void pfactors_rec(int, int);
void pfactors(int);
int main()
{
int num;
printf("Enter a positive integer number\n");
scanf("%d", &num);
printf("\nPrime Factors of %d without using recursion\n", num);
pfactors(num);
printf("\nPrime Factors of %d using recursion\n", num);
pfactors_rec(num, 2);
return 0;
}
void pfactors_rec(int num, int count)
{
if(num < 1)
return;
else if(num % count == 0)
{
printf("%d\n", count);
pfactors_rec(num / count, count);
}
else
{
pfactors_rec(num, count+1);
}
}
void pfactors(int num)
{
int count;
for(count = 2; (num > 1); count++)
{
while(num % count == 0)
{
printf("%d\n", count);
num = num / count;
}
}
printf("\n");
}
Output 1: Enter a positive integer number 24
Prime Factors of 24 without using recursion 2 2 2 3
Prime Factors of 24 using recursion 2 2 2 3
Output 2: Enter a positive integer number 35
Prime Factors of 35 without using recursion 5 7
Prime Factors of 35 using recursion 5 7
Output 3: Enter a positive integer number 510
Prime Factors of 510 without using recursion 2 3 5 17
Prime Factors of 510 using recursion 2 3 5 17
Output 4: Enter a positive integer number 24024
Prime Factors of 24024 without using recursion 2 2 2 3 7 11 13
Prime Factors of 24024 using recursion 2 2 2 3 7 11 13
Output 5: Enter a positive integer number 315
Prime Factors of 315 without using recursion 3 3 5 7
Prime Factors of 315 using recursion 3 3 5 7
Logic To Find Prime Factors of a Number using Recursion
We pass the user input number and 2 to the recursive function pfactors_rec(). We pass 2 as count value because 2 is the first prime number. So we initialize 2 to count and we change the value of count inside pfactors_rec() function.
Inside pfactors_rec() function We first write the base condition(i.e., a condition to exit or return from the infinite recursive calls – freeing up the memory stack). We check if num value is less than 1, in that case we return the control back to the calling function.
Inside else if condition we check if the user input number is perfectly divided by 2(initial value of variable count). If true, then we print the value 2 and then divide the number by 2. We keep doing this recursively until num is not perfectly divided by 2.
If 2 can’t perfectly divide the number then, else condition code is executed, where we increment the value of count by 1.
Since inside else if we keep dividing the number by value of count until it perfectly divides the number, the multiples of value of count can not divide the number going further. So only prime numbers can(probably) perfectly divide the value present inside variable num. This is the reason we need not write function to find next prime number and then assign it to count.
Example with output
num
count
num%count
function call
Print
24
2
true
pfactor_rec (24/2, 2)
2
12
2
true
pfactor_rec (12/2, 2)
2
6
2
true
pfactor_rec (6/2, 2)
2
3
2
false
pfactor_rec (3, 2+1)
3
3
true
pfactor_rec (3/3, 3)
3
Since num = 1, base condition gets executed and all the function instances of pfactors_rec() and associated memory gets popped out of the stack and finally the prime factors of the user input number will be left out on the console window.
Logic To Find Prime Factors of a Number using Iterative Logic
If user input number is perfectly divisible by 5, then we iteratively or recursively or repeatedly divide the number by 5, until the number is no longer perfectly divisible by the number 5. That way, going forward, no other numbers which are multiples of 5 can perfectly divide the number.
For Example: If user input number is 24, and you continously divide the number 24 by 2 until 2 doesn’t perfectly divide the number, then no other multiples of 2 can perfectly divide the number.
Step 1:
num = 24, count = 2;
24 % 2 == 0 (True) 24 / 2 = 12;
Step 2:
num = 12, count = 2;
12 % 2 == 0 (True) 12 / 2 = 6;
Step 3:
num = 6, count = 2;
6 % 2 == 0 (True) 6 / 2 = 3;
Step 3:
Now num is reduced to 3, so no other numbers which are multiples of number 2 can perfectly divide the number(which happens to be 3 in this case).
Check steps 1, 2 and 3 for any number. Ultimately, only prime numbers can perfectly divide any number. Take a pen and paper and give it a try.