SKTN Solutions For C Part 4 - Online Article

Introduction

The tutorial series "SKTN Solutions for C" is again continued with this tutorial. In this part 4 of the series, we will be discussing recursion related problems. As it seems to most of us that recursion is somewhat difficult than general C concepts, I decided to devote a whole tutorial on questions of recursion. I hope you will enjoy and understand. So, let us once again delve into the ocean of C.

Problem 16: Write a program to calculate the sum of digits of a five digit number using recursion.

Every single part of a number is called a digit. For example in the number 123, the digits are 1, 2 and 3. Therefore, sum of digits of a five digit number 12345 is 1+2+3+4+5 = 15. To solve this problem, we will use % (modulus) operator of C. This operator divides first number by second and returns the remainder. For example: 10%3 = 1 and 15%4 = 3. Now, we will use this % (modulus) operator to extract each digit of the five digit number and then we will add them.

In recursion, the most important point is to decide the stopping condition. A stopping condition is the point in the execution of a program when the function stops calling itself. To understand these concepts, we will have to look the code first. Let us C the code now,

#include <stdio.h>
#include <conio.h>
int sum(int n)
{
	if(n == 0)
		return (0);
	else
		return ((n%10) + sum(n/10));
}
void main()
{
	printf("Sum of digits of 12345 is %d",sum(12345));
	getch();
}

In the main function, the function sum is called in the printf. The value of 12345 is passed to sum in the form of n. Now, every time the function sum is called, the following process happen,

  • If n is zero, then zero is returned. This is the stopping condition for the recursion.
  • If n is not zero, the remainder of n divided by 10 is added with the value returned by calling the function sum with parameter n/10.

In this way, the number gets reduced by a factor of 10 every time the recursive function sum is called and the digit extracted by n%10 is added. At last, we get the sum of digit which is printed in main using printf. The getch() function is optional and is used just to halt the screen until the user hits the enter key. To get sum of digit of a different number, just change the value passed to the sum function in printf from 12345 to the desired number.

Problem 17: Write a program to calculate the prime factors of a number using recursion.

The prime factors of a number are the lowest prime numbers by which a number can be fully divided. For example: prime factor of 24 is 2, 2, 2 and 3 because 2*2*2*3 = 24. Another example is 50 whose prime factors are 2, 5 and 5.

Thus, the problem basically extends the prime numbers generating problem. To understand this problem, please understand the program to print the prime numbers (Problem 11 and 14 of tutorial 3 of this series). Let us C the code now,

#include <stdio.h>
#include <conio.h>
int isPrime(int num)
{
	int flag = 1, j;
	for(j=2; j<=num/2; j++)
		if(num%j == 0)
			flag = 0;
	return (flag);
}
void pf(int n)
{
	int i=2;
	for(i=2; n!=1; i++)
		if(isPrime(i) == 1)
			if(n % i == 0)
			{
				printf("\t%d",i);
				pf(n/i);
				return;
			}
}
void main()
{
	pf(24);
	getch();
}

A function isPrime calculates whether a number (num) is prime number or not. If it prime then, 1 is returned else 0 is returned. In the main function, the function pf is called. The value of 24 is passed to pf in the form of n. Now, every time the function pf is called, the following process happen,

  • In the for loop, the value of i increments every time starting from 2. The loop runs until n becomes 1.
  • Every time i is checked. If it is a prime number, then it is checked whether the number can be divided completely by i. If i divides the number then,
    • Value of i is printed on the screen by using printf.
    • The function pf is called with the parameter n/i.
    • The function pf is ended and the control is returned by using return.

In this way, the prime factors of a number are printed on the screen. The getch() function is optional and is used just to halt the screen until the user hits the enter key. To get prime factors of a different number, just change the value of parameter passed to pf in the main function from 24 to the desired number.

Problem 18: Write a program to display and sum the Fibonacci series up to the value 10000 using recursion.

In the Fibonacci series, any term is sum of previous two terms. The first two terms of the series are taken as 0 and 1. So, the series becomes,

0, 1, 1, 2, 3, 5, 8, 13, 21 ...

Let us C the code now,

#include <stdio.h>
#include <conio.h>
int fib(int a, int b)
{
	int c = a+b;
	a = b;
	b = c;
	if(a <= 10000)
	{
		printf("\t%d",a);
		return (a + fib(a,b));
	}
	else
		return (0);
}
void main()
{
	printf("\nSum is %d", fib(0,1));
	getch();
}

In the main function, the function fib is called with the parameters 0 and 1 in the printf because 0 an 1 are the first two fixed values of the Fibonacci series. Now, every time the function fib is called, the following process happen,

  • The two values are received in a and b.
  • Values of a and b are added to c.
  • Value of b is stored in a.
  • Value of c is stored in b.
  • If a is less than or equal to 10000 then
    • Value of a is printed on the screen.
    • The value of a is added to the value returned by calling the function fib with a and b.
  • If a is more than 10000 in step
  • then zero is returned.

In this way, the Fibonacci series is printed on the screen. The getch() function is optional and is used just to halt the screen until the user hits the enter key.

Problem 19: Write a program to convert a decimal number to its binary equivalent using recursion.

The number system we use in our daily life is decimal number system. This number system is of base 10. This means that after every 10 counting one digit increases. But the binary number system is of base 2, i.e. after every 2 counting one digit increases. To understand, see the conversion table below:

Decimal Binary Decimal Binary Decimal Binary
0 0 8 1000 16 10000
1 01 9 1001 17 10001
2 10 10 1010 18 10010
3 11 11 1011 19 10011
4 100 12 1100 20 10100
5 101 13 1101 21 10101
6 110 14 1110 22 10110
7 111 15 1111 23 10111

The standard way to convert decimal to binary is to divide the decimal number by 2 and note the remainder. We continue this process until the number becomes zero. The remainders we have noted in this process are then read in opposite direction and we get the binary equivalent. See example in the accompanying figure. Here, the number 6 is in decimal which is successively divided by 2 and the remainder 0, 1 and 1 are noted. When these are read in opposite direction, it makes 110, which is the octal equivalent of 6.

Image1

Let us C the code now,

#include <stdio.h>
#include <conio.h>
void bin(int n)
{
	int a; if(n != 0)
	{
		a=n%2;
		bin(n/2);
		printf("%d",a);
	}
}
void main()
{
	bin(20);
} 

In the main function, the function bin is called in the printf. The value of 20 is passed to bin in the form of n. Now, every time the function bin is called, the following process happen,

If n is not zero, then

  • The remainder of n divided by 2 is stored in a.
    • The function bin is called with parameter n/2.
    • The value of a is printed on the screen by using printf.

In this way, the number gets reduced by a factor of 2 every time the recursive function bin is called and the digit extracted by n%2 is printed. At last, we get the binary equivalent of the decimal number. The getch() function is optional and is used just to halt the screen until the user hits the enter key. To get binary equivalent of a different number, just change the value passed to the bin function in printf from 20 to the desired number.

Problem 20: Write a program to calculate the sum of first 25 natural numbers using recursion.

Sum of first 25 natural numbers means summing 1+2+3+4+5+...+23+24+25. In recursion, the most important point is to decide the stopping condition. A stopping condition is the point in the execution of a program when the function stops calling itself. To understand these concepts, we will have to look the code first. Let us C the code now,

#include <stdio.h>
#include <conio.h>
int sum(int n)
{
	if(n == 0)
		return 0;
	else
		return (n + sum (n-1));
}
void main()
{
	printf("Sum of first 25 number is %d",sum(25));
} 

In the main function, the function sum is called in the printf. The value of 25 is passed to sum in the form of n. Now, every time the function sum is called, the following process happen,

  • If n is zero, then zero is returned. This is the stopping condition for the recursion.
  • If n is not zero, n is added with the value returned by calling the function sum with parameter n-1.

In this way, the number gets added with their successive previous number starting from n that is 25. At last, we get the sum of digit which is printed in main using printf. The getch() function is optional and is used just to halt the screen until the user hits the enter key. To get sum of different numbers, just change the value passed to the sum function in printf from 25 to the desired number.

About the Author:

No further information.




Comments

No comment yet. Be the first to post a comment.