POWER  OF A NUMBER USING RECURSION and nCr USING RECURSION

POWER  OF A NUMBER USING RECURSION and nCr USING RECURSION 

In this article, we are going to have a look at nCr USING RECURSION and POWER  OF A NUMBER USING RECURSION.

INTRODUCTION: nCr USING RECURSION

In this tutorial, we are going to calculate the combination formula, nCr using recursion

The nCr is a combination that is known for the selection of things without considering the order of the arrangement. This formula is used to find the possible arrangements where a selection of things is done without consideration of the order.

For example:
Input n = 5 r = 2

Output: 10.

APPROACH 1

In this tutorial, we are going to calculate the combination formula, nCr using recursion

The nCr is a combination that is known for the selection of things without considering the order of the arrangement. This formula is used to find the possible arrangements where a selection of things is done without the consideration of the order.

For example:
Input n = 5 r = 2

Output: 10.

ALGORITHM

Step 1: Start.
Step 2: recursive function will call itself until the value of r is lesser than n.
Step 3: until the base condition of the function is satisfied, we will recursively call the function and store the returned value. The base condition of the function is.

If r==0 or r==n return 1
If n<r return 0
Else return (n - 1, r - 1) + (n - 1, r)

Step 4: Stop.

C++ Code:

#include <iostream>
using namespace std;
int nCr(int n, int r) {
    if (r > n) return 0;
    if (r == 0 || r == n) return 1;
    return nCr(n - 1, r - 1) + nCr(n - 1, r);
}
int main() {
    int n,r;
    cin>>n>>r;
    int NCR =  nCr(n,r);
    cout<<NCR;
}

Python code:

def nCr(n,r):
  if r==0 or r==n:
    return 1
  if n<r:
    return 0
  return nCr(n - 1, r - 1) + nCr(n - 1, r)
n = int(input())
r = int(input())
print(nCr(n,r))

JAVA code:

import java.util.*;
public class Main {
  static int nCr(int n, int r) {
    if (r > n) return 0;
    if (r == 0 || r == n) return 1;
    return nCr(n - 1, r - 1) + nCr(n - 1, r);
}
    public static void main(String[] args) {
      Scanner s = new Scanner(System.in);
      int n = s.nextInt();
      int r = s.nextInt();
      int NCR = nCr(n,r);
      System.out.println(NCR);
  }
}
Input: 5 2

Output: 10

The time complexity of the code is O(2n).
The space complexity of the code is O(N2).

INTRODUCTION: POWER  OF A NUMBER USING RECURSION

In this tutorial, we are going to calculate the fPOWER  OF A NUMBER USING RECURSION.

See also  Recursive Implementation of Binary Search

Given an integer N, write a program to calculate the power of a number using recursion.

Ex1:

Input : base=2 and power=2

Output:   4

Ex2:

Input N:   base=2 and power=3

Output:   8

APPROACH 1

We will transform the above mathematical function as follows:

  1. First, give a meaningful name to our recursive function say power()

2. The function must accept two numbers i.e., base and expo, and calculate its power. Hence, take two parameters for base and exponent, say power(int base, int expo);

LOGIC

Logic to calculate the power of a number using recursion

After declaring the pow() function it’s time to define logic to find power recursively. There can be three cases while calculating the power of a number.

  • If the exponent is 0, then the power is 1. This is the base condition of our recursive function.
  • If the exponent is negative, then the power is 1 / (x ^ -y). Which uses a recursive call to the pow() function for computing the value of (x ^ -1) i.e. 1 / pow(base, -expo).
  • If the exponent is positive, then calculate power normally using x ^ y. Computing x ^ y also makes a recursive call i.e. base * pow(base, expo – 1)

Let us combine all three conditions in a single recursive function.

ALGORITHM


STEP-1:Start
STEP-2: take input base,exponent
STEP-3: Base condition of recursion:A*o=1;(anything to the power of 0 is 1).

STEP-4: To calculate An ,we can first calculate A*n-1 and then multiply it with A(A*n=A x A*n-1) and store it in result

STEP-5:Stop.

C++ Code:

#include <iostream>
using namespace std;

int power(int base, int expo){
  if(expo == 0) return 1;
  else return base*power(base,expo-1);
}
int main() 
{
    int base,expo;
    cout<<"enter base and exponent values: ";
    cin>>base>>expo;
    cout<<"result is: "<<power(base,expo);
}

Python code:

def power(base,expo):
    if expo==0:
        return 1
    elif expo>0:
        return base*power(base,expo-1)
    else:
        return 1/power(base,-exponent)
base=int(input("enter the number"))
expo=int(input("enter power of a number"))
result=power(base,expo)
print(result)

JAVA code:  

import java.util.*;
public class Basic
{
public static void main(String[] args){
    Scanner reader =new Scanner(System.in);
    int base =reader.nextInt();
    System.out.println("enter power:");
    int expo=reader.nextInt();
    int result=power(base,expo);
    System.out.println("power of number is:"+result);
}
public static int power(int base,int expo)
{
    if(expo==0){
        return 1;
    }
    else{
        return base*power(base,expo-1);
    }
}

}
OUTPUT:
Enter base:
3
enter power:
2
power of number is:9

TIME COMPLEXITY OF THE CODE IS: O(n)

CONCLUSION

CONCLUSION

See also  Horner's Rule and Recurrence Relation

That’s it from this tutorial. Hope you guys found it interesting. We have solved the ncr and the power of a number in different programming languages. Happy coding!

Leave a Comment

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

we provide projects, courses, and other stuff for free. in order for running we use Google ads to make revenue. please disable adblocker to support us.