Source Code: C Program To Find Sum of Natural Numbers Using Recursion
#include
int sum(int num)
{
if(num)
return(num + sum(num-1));
else
return 0;
}
int main()
{
int count = 25;
printf("Sum of 1st 25 natural numbers is %d\n", count, sum(count));
return 0;
}
Output: Sum of 1st 25 natural numbers is 325
Logic To Find Sum of Natural Numbers Using Recursion
25 is passed to a function sum, from main method. Inside function sum(), if the passed number is a non-zero then we add sum(num-1) to num. We keep doing it until num value is 0. Once num is 0, code inside else block gets executed and 0 is returned.
Source Code: Find Sum of Natural Numbers Using Recursion – Take input from user
#include
int sum(int num)
{
if(num)
return(num + sum(num-1));
else
return 0;
}
int main()
{
int count;
printf("Enter a positive no\n");
scanf("%d", &count);
printf("Sum of 1st %d natural numbers is %d\n", count, sum(count));
return 0;
}
Output 1: Enter a positive no 5 Sum of 1st 5 natural numbers is 15
Output 2: Enter a positive no 14 Sum of 1st 14 natural numbers is 105
Example:
Lets assume user has input num value as 5. Recursive Call sum(num – 1).
num
Calling Function
Returned Value
5
sum(5)
5
sum(4)
10
4
sum(3)
6
3
sum(2)
3
2
sum(1)
1
1
sum(0)
0
0
return 0;
Value Returning – Control Shifting back.
num+sum(num-1)
Return Value
Result
1 + sum(0)
0
1 + 0 = 1
2 + sum(1)
1
2 + 1 = 3
3 + sum(2)
3
3 + 3 = 6
4 + sum(3)
6
4 + 6 = 10
5 + sum(4)
10
5 + 10 = 15
Finally, after completing the recursive calls and once num is equal to zero, sum() will return 15 to main().
Source Code: C Program To Print Natural Numbers using Recursion
#include
void display(int);
int main()
{
int limit;
printf("Enter the number of terms to be printed\n");
scanf("%d", &limit);
printf("\nNatural Numbers from 1 To %d are:", limit);
display(limit);
return 0;
}
void display(int num)
{
if(num)
display(num-1);
else
return;
printf("\n%d\n", num);
}
Output: Enter the number of terms to be printed 14
Natural Numbers from 1 To 14 are: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
Logic To Print Natural Numbers using Recursion
We ask the user to input the limit or the number of terms of natural numbers to be printed. We store that value inside variable limit. We pass this value to a function called display().
Inside display() function We check if number is not zero, in that case we call the same function display() recursively and pass (num-1) to it. In the else block we write the base condition, that is, return the control back to the calling function if num is 0.
This prints the natural numbers from 1 to user input limit.
Example:
If limit = 5. We copy the value of limit to num. So num = 5.
Source Code: C Program To Reverse a Number using Recursion
#include
#include
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
#include
#include
int reverse(int num)
{
return( (num>0) ?
((num%10) * pow(10, (int)log10(num)) + reverse(num/10)) :
0);
}
int main()
{
int num, isNegative = 1, result;
printf("Enter a number to reverse\n");
scanf("%d", &num);
isNegative = (num < 0);
if(isNegative)
num *= -1;
result = reverse(num);
if(isNegative)
{
num *= -1;
result *= -1;
}
printf("Reverse of %d is %d\n", num, result);
return 0;
}
Output 1: Enter a number to reverse 123 Reverse of 123 is 321
Output 2: Enter a number to reverse -123 Reverse of -123 is -321
Source Code: C Program To Reverse a Number using Recursion without using log10() function
#include
#include
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
Source Code: C Program To Generate Fibonacci Series using Recursive Function
#include
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:
We already know that fib(2) and fib(3) are both equal to 1.
fib(5) = [1 + 1] + 1; fib(5) = 2 + 1; fib(5) = 3;
So the fifth term in the Fibonacci series is 3.
Source Code: Exact Solution For Above Problem Statement
#include
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)
{
if(num == 1 || num == 2)
return(1);
else
return( fib(num-1) + fib(num-2) );
}
Output: 1. 1
2. 1
3. 2
4. 3
5. 5
6. 8
7. 13
8. 21
9. 34
10. 55
11. 89
12. 144
13. 233
14. 377
15. 610
16. 987
17. 1597
18. 2584
19. 4181
20. 6765
21. 10946
22. 17711
23. 28657
24. 46368
25. 75025
Source Code: Generate 25 terms in Fibonacci Series using Recursion and Ternary/conditional operator
#include
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.
A 5-digit positive integer is entered through the keyboard, write a recursive and a non-recursive function to calculate sum of digits of the 5-digit number.
Analyze The Problem Statement
1. User enters a 5-digit number. 2. We need to write 2 functions to calculate sum of digits of user entered number. 3. One function should use recursive logic and the other should calculate sum of digits without using recursion.
Source Code: C Program To Calculate Sum of Digits Using Recursion
#include
int add(int);
int add_rec(int);
int main()
{
int num;
printf("Enter a 5-digit positive integer number\n");
scanf("%d", &num);
printf("Sum of Digits(without using recursion): %d\n", add(num));
printf("Sum of Digits(using recursion): %d\n", add_rec(num));
return 0;
}
int add(int num)
{
int sum = 0;
while(num)
{
sum = sum + (num % 10);
num = num / 10;
}
return(sum);
}
int add_rec(int num)
{
if(num)
return( (num % 10) + add_rec(num / 10) );
else
return 0;
}
Output 1: Enter a 5-digit positive integer number 12345 Sum of Digits(without using recursion): 15 Sum of Digits(using recursion): 15
Output 2: Enter a 5-digit positive integer number 15937 Sum of Digits(without using recursion): 25 Sum of Digits(using recursion): 25
Logic To Calculate Sum of Digits without using Recursion
1. Using (num % 10), we fetch the last digit of the user entered number and add it to the previous value of sum. 2. Next we reduce the uer entered number by 1 digit(from the right end) by dividing the number by 10 i.e., num / 10. 3. We put above two steps/logic into while loop. We iterate through the while loop until num is positive. Once num value is 0, control exits the while loop. 4. Outside while loop we return the value present in variable sum – which will have the sum of all the individual digits of the user entered number. If num = 12345;
num
num%10
sum
num/10
12345
5
5
1234
1234
4
9
123
123
3
12
12
12
2
14
1
1
1
15
0
If you observe above table, when num becomes 0, sum has 15 in it. So 15 is the sum of all the individual digits of the user entered number 12345.
So at the end 15 is returned back to main() method and the result is printed on the console window.
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 out of the memory stack immediately after returning the value.
You can even write the recursive logic to find sum of digits of a number using above ternary or conditional operator.
Source Code: C Program To Calculate Sum of Digits Using Recursion And Ternary Operator
#include
int add(int);
int add_rec(int);
int main()
{
int num;
printf("Enter a 5-digit positive integer number\n");
scanf("%d", &num);
printf("Sum of Digits(without using recursion): %d\n", add(num));
printf("Sum of Digits(using recursion): %d\n", add_rec(num));
return 0;
}
int add(int num)
{
int sum = 0;
while(num)
{
sum = sum + (num % 10);
num = num / 10;
}
return(sum);
}
int add_rec(int num)
{
return( ( num > 0 ) ? ( (num % 10) + add_rec(num / 10) ) : 0 );
}
Output 1: Enter a 5-digit positive integer number 12345 Sum of Digits(without using recursion): 15 Sum of Digits(using recursion): 15
Output 2: Enter a 5-digit positive integer number 98654 Sum of Digits(without using recursion): 32 Sum of Digits(using recursion): 32