Showing posts with label Recursion. Show all posts
Showing posts with label Recursion. Show all posts
Friday, 12 August 2016
Sunday, 31 July 2016
Ackermans function using Recursion
Recursion: Ackerman's Function
Write a program for Ackerman's function using Recursion
Ack(3,0) = ack(2,1)
= ack(1, ack(2,0))
= ack(1, ack(1,1))
= ack(1, ack(0, ack(1,0)))
= ack(1, ack(0, ack(0, 1)))
= ack(1, ack(0, 2))
= ack(1, 3)
= ack(0, ack(1, 2))
= ack(0, ack(0, ack(1, 1)))
= ack(0, ack(0, ack(0, ack(1, 0))))
= ack(0, ack(0, ack(0, ack(0, 1))))
= ack(0, ack(0, ack(0, 2)))
= ack(0, ack(0, 3))
= ack(0, 4)
= 5
#include<stdio.h>
double acker(int
m, int n);
void main()
{
int
m, n;
double
a;
printf("\nEnter
the value of m and n:");
scanf("%d
%d", &m, &n);
if(m<0
|| n<0)
printf("\nEnter
nonnegatives only");
a
= acker(m, n);
printf("\n
A(%d , %d) = %lf", m, n, a);
}
double acker(int
m, int n)
{
if(
m == 0 )
return
n+1;
else
if(n == 0)
return acker((m-1),
1);
else
return acker(
(m-1), acker(m, n-1) );
}
Output:
Enter the value of
m and n: 3 0
A(3 , 0) = 5.000000
Tower of Hanoi problem with n disks
Recursion: Tower of Hanoi
Write a program to solve Tower of Hanoi problem with n disks
#include<stdio.h>
#include<math.h>
void tower(int n, char from_peg, char aux_peg, char to_peg);
void main()
{
int
n;
printf("\nEnter
the number of disks: ");
scanf("%d",
&n);
tower(n,
'A', 'B', 'C'); //
A-> from_peg B->aux_peg C->to_peg
printf("\nTotal number of moves =
%.0lf", pow(2,n)-1 );
}
void tower(int n,
char from_peg, char aux_peg, char
to_peg)
// A-> from_peg B->aux_peg
C->to_peg
{
if(n
== 1)
{
printf("\nMove
disk %d from %c peg to %c peg", n,
from_peg, to_peg);
return;
}
// move n-1 disks from
A(from_peg) to B(to_peg) using C(aux_peg) as auxiliary
tower(n-1, from_peg, to_peg,
aux_peg);
printf("\nMove disk %d from
peg %c to %c peg", n, from_peg,
to_peg);
// move n-1 disks from B(aux_peg)
to C(to_peg) using A(from_peg) as auxiliary
tower(n-1,
aux_peg, from_peg, to_peg);
}
Output:
Enter the number
of disks: 3
Move disk 1 from A peg to C peg
Move disk 2 from peg A to B peg
Move disk 1 from C peg to B peg
Move disk 3 from peg A to C peg
Move disk 1 from B peg to A peg
Move disk 2 from peg B to C peg
Move disk 1 from A peg to C peg
Total
number of moves = 7
N Fibonacci series using Recursion
Recursion: Fibonacci Series
Write a program to print N Fibonacci terms using Recursion.
#include<stdio.h>
int fib(int n);
void main()
{
int
i, n;
printf("\nEnter
the value of n:");
scanf("%d",
&n);
printf("\n
%d fibonacci terms are: ", n);
for(i=0;
i<n; i++)
printf("%d
", fib(i));
}
int fib(int n)
{
if(n
== 0)
return
0;
else
if(n == 1)
return
1;
else
return
(fib(n-1) + fib(n-2));
}
Output:
Enter the value of
n: 10
10 fibonacci terms
are:
0 1
1 2 3 5 8
13 21 34
GCD of two numbers using Recursion
Recursion: Greatest Common Divisor using Euclid's Algorithm
Write a program to find a GCD of two numbers using Recursion.
#include<stdio.h>
int gcd(int a, int
b);
void main()
{
int
a, b, g;
printf("\nEnter
the value of a and b:");
scanf("%d%d",
&a, &b);
g
= gcd(a, b) ;
printf("\n GCD = %d",
g);
}
int gcd(int a, int
b)
{
if(b
== 0)
return
a;
else
return
gcd(b, a%b);
}
Output:
Enter the value of
a and b: 4 6
GCD = 2
Factorial of a Number using Recursion
Recursion: Factorial
Write a program to find a Factorial of a Given Number using Recursion.
#include<stdio.h>
long int fact (int
n);
void main()
{
int n;
long
int f;
printf("\nEnter
the value of n: ");
scanf("%d",
&n);
f
= fact(n) ;
printf("\nFactorial
of given number %d is %ld", n, f);
}
long int fact(int
n)
{
if(
n == 0)
return
1;
else
return
n*fact(n-1);
}
Output:
Enter the value of
n: 5
Factorial of given
number 5 is 120
Subscribe to:
Posts (Atom)