C Programming
Recursion
What is Recursion?
Recursion: It is a process by which a function calls itself repeatedly
until some specified condition has been satisfied
It is a processing of defining something in terms of itself.
A function is called recursive if a statement within the body of a
function calls the same function.
Example: Factorial Calculation
How to calculate 5!?
5 * 4 * 3 * 2 * 1 = 120
i.e., 5 * 4! (Or) 5 * 4 * 3!
(Or) 5 * 4 * 3 * 2! (Or) 5 * 4 * 3 * 2 * 1! (Or) 5 * 4 * 3 * 2 * 1
So, n! = n * (n-1)!
Factorial in C Language
#include <stdio.h>
int main()
{ int a, fact;
printf (“Enter any number”);
scanf (“%d”,&a);
fact = factorial(a);
printf (“Factorial Value:%d”,fact);
}
int factorial (int x)
{ int f=1,i;
for(i=x;i>=1;i--)
f = f * I;
return(f);
}
Factorial - Iteration
int Factorial (int x) If x=5 means
{ int f=1,i; Before iteration Loop 1
f = 1; i = 5; for (i=x; i>=1) - - - for i = 5 & 5 >=1
for(i=x;i>=1;i--) f = f * i; - - - f = 1 * 5; then f = 5
f = f * i; i - -; - - - then i=4;(5-1)
return(f);
} Loop 2
for (i=x; i>=1) - - - for i = 4 & 4 >=1
f = f * i; - - - f = 5 * 4; then f = 20
i - -; - - - then i=3;(4-1)
Return (f) Loop 3
Return (120) for (i=x; i>=1) - - - for i = 3 & 3 >=1
f = f * i; - - - f = 20 * 3; then f = 60
i - -; - - - then i=2;(3-1)
Loop 4
Loop 5 for (i=x; i>=1) - - - for i = 2 & 2 >=1
for (i=x; i>=1) - - - for i = 1 & 1 >=1 then f = f * i; - - - f = 60 * 2; then f = 120
condition is false. Break;
i - -; - - - then i=1;(2-1)
Factorial using Recursion
#include <stdio.h> int rec(int x)
int main() {
int f;
{ int a, fact; Function “rec”
printf (“Enter any number”); if (x==1) is calling itself
return 1;
scanf (“%d”,&a); else
fact = rec(a); f = x * rec (x-1);
printf (“Factorial Value:%d”,fact);
return (f)
} }
Control flows of recursive call
from main()
If x != 1 If x != 1 If x == 1
int rec(int x) int rec(int x) int rec(int x) int rec(int x)
{ { { {
int f; int f; int f; int f;
if (x==1) if (x==1) if (x==1) if (x==1)
return 1; return 1; return 1; return 1;
else else else else
f = x * rec (x-1); f = x * rec (x-1); f = x * rec (x-1); f = x * rec (x-1);
return (f) return (f) return (f) return (f)
} } } }
to main()
Recursive call with an example
from main()
If x =
4
int rec(4) int rec(3) int rec(2) int rec(1)
{ { { {
int f; int f; int f; int f;
if (4==1) if (3==1) if (2==1) if (1==1)
return 1; return 1; return 1; return 1;
else else else else
f = 4 * rec (4-1); f = 3 * rec (3-1); f = 2 * rec (2-1); f = x * rec (x-1);
return (24) return (6) return (2) return (f)
} } } }
to main()
rec(4) returns 4 rec(3) returns 3 rec(2) returns 2 rec(1) returns 1
times of rec(3) times of rec(2) times of rec(1) time of rec(1)
Query?
The End
