State some examples of recursive functions?

Started by chinmay.sahoo, 04-04-2016, 04:22:57

Previous topic - Next topic

chinmay.sahooTopic starter

Examples of recursive functions are as follows:-
Factorial of a given number
Palindrome
Fibonnaci series
GCD


friendhrm

#1
here are some examples of recursive functions:

1. Factorial function:
function factorial(n) {
  if (n <= 1) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}


2. Fibonacci sequence:
def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)


3. Binary search:
int binarySearch(int[] arr, int left, int right, int x) {
    if (right >= left) {
        int mid = left + (right - left) / 2;
       
        if (arr[mid] == x) {
            return mid;
        }
       
        if (arr[mid] > x) {
            return binarySearch(arr, left, mid - 1, x);
        }
       
        return binarySearch(arr, mid + 1, right, x);
    }
   
    return -1;
}


4. Print numbers in a range:
function printRange(start, end) {
  if (start > end) {
    return;
  } else {
    console.log(start);
    printRange(start + 1, end);
  }
}


5. Power function:
def power(base, exponent):
    if exponent == 0:
        return 1
    else:
        return base * power(base, exponent - 1)


6. Tree traversal:
void inOrderTraversal(Node node) {
    if (node != null) {
        inOrderTraversal(node.left);
        System.out.print(node.data + " ");
        inOrderTraversal(node.right);
    }
}


These examples demonstrate the versatility of recursive functions and how they can be applied to various problem-solving scenarios.


The rule of thumb for recursion is, "Use recursion, if and only if on each iteration your task splits into two or more similar tasks".

So Fibonacci is not a good example of recursion application, while Hanoi is a good one.

So most of the good examples of recursion are tree traversal in different disquises.

For example: graph traversal - the requirement that visited node will never be visited again effectively makes graph a tree (a tree is a connected graph without simple cycles)

divide and conquer algorithms (quick sort, merge sort) - parts after "divide" constitute children nodes, "conquer" constitues edges from parent node to child nodes.