CH-6 RECURSION

What is Recursion?
◻ Any function which calls itself is called recursive function and such
function calls are called recursive calls.
◻ Recursion cannot be applied to all problems, but it is more useful for
the tasks that can be defined in terms of a similar subtask.
◻ It is idea of representing problem a with smaller problems.
◻ Any problem that can be solved recursively can be solved
iteratively.
◻ When recursive function call itself, the memory for called function
allocated and different copy of the local variable is created for each
function call.
◻ Some of the problem best suitable for recursion are
Factorial
Fibonacci
Tower of Hanoi
Working of Recursive function
Working
void func1();

void main()
{
....
func1();
.... Function
} call

void func1()
{ Recursive
.... function call
func1();
....
}
Properties of Recursion
◻ A recursive function can go infinite like a loop. To
avoid infinite running of recursive function, there are
two properties that a recursive function must have.
◻ Base Case or Base criteria
It allows the recursion algorithm to stop.
A base case is typically a problem that is small enough to
solve directly.
◻ Progressive approach
A recursive algorithm must change its state in such a way
that it moves forward to the base case.
Recursion - factorial example
Recursive trace

Final Ans 5 *24 = 120

Fact(5)
return 4 * 6 = 24
call
Fact(4)
return 3 * 2 = 6
call
◻ The factorial of a integer n, is product of Fact(3)
n * (n-1) * (n-2) * …. * 1 return 2 * 1 = 2
call
◻ Recursive definition of factorial
n! = n * (n-1)! Fact(2)
Example return 1
call
■ 3! = 3 * 2 * 1
■ 3! = 3 * (2 * 1) Fact(1)
■ 3! = 3 * (2!)
WAP to find factorial of given number using
Recursion

Program Output
1 #include <stdio.h> Enter the number? 5
2 int fact(int); factorial = 120
3 void main()
4 {
5 int n, f;
6 printf("Enter the number?\n");
7 scanf("%d", &n);
8 f = fact(n);
9 printf("factorial = %d", f);
10 }
11 int fact(int n)
12 {
13 if (n == 0)
14 return 1;
15 else if (n == 1)
16 return 1;
17 else
18 return n * fact(n - 1);
19 }
Recursion - Fibonacci example
Recursive trace
◻ A series of numbers , where next Fib(4) Final Ans. 3
number is found by adding the two return 1
return 2
number before it.
◻ Recursive definition of Fibonacci Fib(3) Fib(2)

Fib(0) = 0 ret
return 1 return 1
Fib(1) = 1 return 1
Fib(2) Fib(1) Fib(1) Fib(0
Fib(n) = Fib(n-1) + Fib(n-2)
◻ Example return 0
return 1
Fib(4) = Fib(3) + Fib(2)
Fib(1) Fib(0)
Fib(4) = 3
WAP to Display Fibonacci Sequence
Program Program contd.
1 #include <stdio.h> 15 int fibonacci(int n)
2 int fibonacci(int); 16 {
3 void main() 17 if (n == 0 || n == 1)
4 { 18 return n;
5 int n, m = 0, i; 19 else
6 printf("Enter Total 20 return (fibonacci(n - 1) +
7 terms\n"); fibonacci(n - 2));
8 scanf("%d", &n); 21 }
9 printf("Fibonacci
10 series\n"); Output
11 for (i = 1; i <= n; i++) Enter Total terms
12 { 5
13 printf("%d ", Fibonacci series
14 fibonacci(m)); 0 1 1 2 3
m++;
}
}
 Recursion - Decimal to Binary
example
Recursive trace
◻ To convert decimal to binary, divide decimal
number by 2 till dividend will be less then 2 Final Ans 13%2 + 10*110 = 1101
◻ To convert decimal 13 to binary decToBin(13)
13/2 = 6 reminder 1 return 6%2 + 10*11 = 110
call
6/2 = 6 reminder 0
3/2 = 3 reminder 1 decToBin(6)
return 3%2 + 10*1 = 11
1/2 = 1 reminder 1 call
◻ Recursive definition of Decimal to Binary decToBin(3)
decToBin(0) = 0 1%2 + 10*0 =
call
decToBin(n) = n%2 + 10* decToBin(n/2) 1
◻ Example decToBin(1)
decToBin(13) = 13%2 + 10 decToBin(6) return 0
call
decToBin(13) = 1101
decToBin(0)
WAP to Convert Binary to Decimal
Program Output
1 #include <stdio.h> Enter a binary number: 101
2 int convertBinaryToDecimal(int b, int c, int t);
3 void main() Decimal value of 101 is 5
4 {
5 unsigned int binary, decimal;
6 printf("Enter a binary number: ");
7 scanf("%d", &binary);
8 decimal = convertBinaryToDecimal(binary, 1, 0);
9 printf("Decimal value of %d is %d", binary, decimal);
10 }
11 int convertBinaryToDecimal(int b, int c, int t)
12 {
13 if (b > 0)
14 {
15 t += (b % 10) * c;
16 convertBinaryToDecimal(b / 10, c * 2, t);
17 }
18 else
19 return t;
20 }
Practice Programs
1) Write a program to find factorial of a given number
using recursion.
2) WAP to convert decimal number into binary using
recursion.
3) WAP to use recursive calls to evaluate F(x) = x – x3/3!
+ x5/5! – x7/7! + … + xn/n!