[go: up one dir, main page]
Scribd
Upload
5 views9 pages

Recursion

The document explains recursion in C programming, highlighting its definition as a function calling itself until a condition is met. It provides examples of calculating factorials both iteratively and recursively, along with code snippets for each method. The document also illustrates the control flow of recursive calls with a detailed example.

Uploaded by

Elamparithi Maniezhilan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
5 views9 pages

Recursion

The document explains recursion in C programming, highlighting its definition as a function calling itself until a condition is met. It provides examples of calculating factorials both iteratively and recursively, along with code snippets for each method. The document also illustrates the control flow of recursive calls with a detailed example.

Uploaded by

Elamparithi Maniezhilan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 9

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

You might also like