Showing posts with label Recursion. Show all posts
Showing posts with label Recursion. Show all posts

Friday 12 August 2016

Sunday 31 July 2016

Recursion

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