1 of 13

Recursion

{C}

Programming

Programming for Problem Solving (PPS)

GTU # 3110003

USING

Prof. Nilesh Gambhava

�Computer Engineering Department,�Darshan Institute of Engineering & Technology, Rajkot

2 of 13

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

Prof. Nilesh Gambhava

#3110003 (PPS) – Recursion

2

3 of 13

Working of Recursive function

void func1();

void main()

{

....

func1();

....

}

void func1()

{

....

func1();

....

}

Function call

Recursive function call

Working

Prof. Nilesh Gambhava

#3110003 (PPS) – Recursion

3

4 of 13

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.

Prof. Nilesh Gambhava

#3110003 (PPS) – Recursion

4

5 of 13

Recursion - factorial example

The factorial of a integer n, is product of

n * (n-1) * (n-2) * …. * 1

Recursive definition of factorial

n! = n * (n-1)!
Example

3! = 3 * 2 * 1
3! = 3 * (2 * 1)
3! = 3 * (2!)

Fact(5)

Fact(4)

Fact(3)

Fact(2)

Fact(1)

call

return 1

return 2 * 1 = 2

return 3 * 2 = 6

return 4 * 6 = 24

Final Ans 5 *24 = 120

Recursive trace

Prof. Nilesh Gambhava

#3110003 (PPS) – Recursion

5

6 of 13

WAP to find factorial of given number using Recursion

#include <stdio.h>

int fact(int);

void main()

{

int n, f;

printf("Enter the number?\n");

scanf("%d", &n);

f = fact(n);

printf("factorial = %d", f);

}

int fact(int n)

{

if (n == 0)

return 1;

else if (n == 1)

return 1;

else

return n * fact(n - 1);

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

Enter the number? 5

factorial = 120

Program

Output

Prof. Nilesh Gambhava

#3110003 (PPS) – Recursion

6

7 of 13

Recursion - Fibonacci example

A series of numbers , where next number is found by adding the two number before it.
Recursive definition of Fibonacci

Fib(0) = 0
Fib(1) = 1
Fib(n) = Fib(n-1) + Fib(n-2)

Example

Fib(4) = Fib(3) + Fib(2)
Fib(4) = 3

Recursive trace

Fib(3)

Fib(4)

Fib(2)

Fib(1)

Fib(0)

Fib(1)

Fib(0)

return 1

return 0

return 1

return 2

return 0

return 1

Final Ans. 3

Prof. Nilesh Gambhava

#3110003 (PPS) – Recursion

7

8 of 13

WAP to Display Fibonacci Sequence

#include <stdio.h>

int fibonacci(int);

void main()

{

int n, m = 0, i;

printf("Enter Total terms\n");

scanf("%d", &n);

printf("Fibonacci series\n");

for (i = 1; i <= n; i++)

{

printf("%d ", fibonacci(m));

m++;

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

Enter Total terms

5

Fibonacci series

0 1 1 2 3

Program

Output

int fibonacci(int n)

{

if (n == 0 || n == 1)

return n;

else

return (fibonacci(n - 1) + fibonacci(n - 2));

}

15

16

17

18

19

20

21

Program contd.

Prof. Nilesh Gambhava

#3110003 (PPS) – Recursion

8

9 of 13

Recursion - Decimal to Binary example

To convert decimal to binary, divide decimal number by 2 till dividend will be less then 2
To convert decimal 13 to binary

13/2 = 6 reminder 1
6/2 = 6 reminder 0
3/2 = 3 reminder 1
1/2 = 1 reminder 1

Recursive definition of Decimal to Binary

decToBin(0) = 0
decToBin(n) = n%2 + 10* decToBin(n/2)

Example

decToBin(13) = 13%2 + 10 decToBin(6)
decToBin(13) = 1101

decToBin(13)

decToBin(6)

decToBin(3)

decToBin(1)

decToBin(0)

call

return 0

return 1%2 + 10*0 = 1

return 3%2 + 10*1 = 11

return 6%2 + 10*11 = 110

Final Ans 13%2 + 10*110 = 1101

Recursive trace

Prof. Nilesh Gambhava

#3110003 (PPS) – Recursion

9

10 of 13

WAP to Convert Decimal to Binary

#include <stdio.h>

int convertDecimalToBinary(int);

void main()

{

int dec, bin;

printf("Enter a decimal number: ");

scanf("%d", &dec);

bin = convertDecimalToBinary(dec);

printf("The binary equivalent = %d \n",bin);

}

int convertDecimalToBinary(int dec)

{

if (dec == 0)

return 0;

else

return (dec % 2 + 10 * convertDecimalToBinary(dec / 2));

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

Enter a decimal number: 12

The binary equivalent = 1100

Program

Output

Prof. Nilesh Gambhava

#3110003 (PPS) – Recursion

10

11 of 13

WAP to Convert Binary to Decimal

#include <stdio.h>

int convertBinaryToDecimal(int b, int c, int t);

void main()

{

unsigned int binary, decimal;

printf("Enter a binary number: ");

scanf("%d", &binary);

decimal = convertBinaryToDecimal(binary, 1, 0);

printf("Decimal value of %d is %d", binary, decimal);

}

int convertBinaryToDecimal(int b, int c, int t)

{

if (b > 0)

{

t += (b % 10) * c;

convertBinaryToDecimal(b / 10, c * 2, t);

}

else

return t;

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

Enter a binary number: 101

Decimal value of 101 is 5

Program

Output

Prof. Nilesh Gambhava

#3110003 (PPS) – Recursion

11

12 of 13

Practice Programs

Write a program to find factorial of a given number using recursion.
WAP to convert decimal number into binary using recursion.
WAP to use recursive calls to evaluate F(x) = x – x³/3! + x⁵/5! – x⁷/7! + … + xⁿ/n!

Prof. Nilesh Gambhava

#3110003 (PPS) – Recursion

12

13 of 13

Thank you

✓