Welcome To Sora Park

Does a function call itself? It's called recursive.

If the function is computed by a loop or repetition, the procedure is called iterative.

Often an iterative approach for the evaluation of a recursively defined sequence requires much less computation than a procedure using recursion.

Fibonacci exemplifies the difference between recursion and iteration.

# Fibonacci Numbers

Fibonacci numbers form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1.

The sequence starts 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

# Recursive Fibonacci

int test(int n)
{
    if (n > 1)
    {
        return test(n - 1) + test(n - 2);
    }
    else
    {
        return n;
    }
}

# Iterative Fibonacci

int test(int n)
{
    if (n > 0)
    {
        int x = 0, y = 1, z;
        for (int i = 1; i < n; i++)
        {
            z = (x + y);
            x = y;
            y = z;
        }
        return y;
    }
    return 0;
}

void test(int input)
{
    if (input > 0)
    {
        printf("%d, ", input);
        test(input - 1);
        printf("%d, ", input);
    }
}

The test function will give the following output back once called:

"3, 2, 1, 1, 2, 3, "

The first print function completes printing out the given input value three times before the second one is called.

This is how the recursive algorithm works!

Recursive algorithms solve a problem by reducing it to an instance of the same problem with smaller input.

Here is a recursive algorithm for computing n factorial (n!):

int test(int input)
{
    printf("%d, ", input);
    if (input == 0)
    {
        return 1;
    }
    else
    {
        return input * test(input - 1);
    }
}

The output is as follows:

"3, 2, 1, 0, "

# Recursive function for exponentiation

The below definition would be very helpful to solve the problem!

a^(n+1) = a * a^n for n > 0 and the initial condition a^0 = 1.

To find a^n, successively use the recursive step to reduce the exponent until it becomes zero.

int test(int base, int input)
{
    if (input > 0)
    {
        test(base, input - 1);
    }

    ans = (input == 0 ? 1 : base * ans);
    printf("%d, ", ans);

    return ans;
}

The output of the function is "1, 2, 4, 8, ".

If someone doesn't want to see the output in the terminal, the below method would be more explicit to understand how the algorithm works:

int test(int base, int input)
{
	if (input == 0)
    {
    	return 1;
    }
    else
    {
    	return base * test(base, input - 1);
    }
}

# Recursive modular exponentiation

The method is based on the fact below:

b^2 mod m = (b * b^(n-1) mod m)) mod m and the initial condition b^0 mod m = 1

However, there is a much more efficient recursive algorithm based on the observation that

In case that n is even, b^n mod m = (b^(n/2) mod m)^2 mod m
In case that n is odd, b^n mod m = ((b^(floor(n/2)) mod m)^2 mod m * b mod m) mod m

int test(int b, int n, int m)
{
    if (n == 0)
    {
        return 1;
    }
    else if (n % 2 == 0)
    {
        ans = pow(test(b, n / 2, m), 2);
        return ans % m;
    }
    else
    {
        ans = pow(test(b, floor(n / 2), m), 2);
        return (ans % m * b % m) % m;
    }
}

# Recursive linear search algorithm

This algorithm is designed to search for the first occurrence of x in the sequence.

int test(int i, int x)
{
    if (arr[i] == x)
    {
        return i;
    }
    else if (i == arr.size() - 1)
    {
        return -1;
    }
    else
    {
        return test(i + 1, x);
    }
}

# Recursive binary search algorithm

This approach is to find the location of x in the sequence of integers in increasing order.

To perform a binary search, it begins by comparing x with the middle term,

a[floor(n+1) / 2]

int test(int i, int j, int x)
{
    m = floor((i + j) / 2);
    if (arr[m] == x)
    {
        return m;
    }
    else if (x < arr[m] && i < m)
    {
        return test(i, m - 1, x);
    }
    else if (x > arr[m] && j > m)
    {
        return test(m + 1, j, x);
    }
    else
    {
        return -1;
    }
}

Linear Search

It begins by comparing x and a1.

When x = a1, the solution is the location of a1.

When x ≠ a1, compare x with a2. If x = a2, the solution is the location of a2.

Continue this process, comparing x successively with each term of the list until a match is found, where the solution is the location of that term unless no match occurs.

This algorithm is also called the sequential search.

# Pseudocode

x: target integer
a1, a2, ... , an: distint integers stored in an array
location: index of x found in the array

procedure()
	i := 1
    while (i is less than or equal to n) and (x is not equivalent to ai) do:
    	i := i + 1
        
    /* if x is found */
    if i is less than or equal to n
    	location := i
    /* if x is not found */
    else 
    	location := 0
return location

Binary Search

It proceeds by comparing the element to be located to the middle term of the list.

The list is split into two smaller sublists of the same size, or where one of them has one fewer term than the other.

The middle term of the list is floor(n / 2), where n is the number of the elements in the list.

Binary Search is much more efficient than Linear Search.

Note that, however, Binary Search can be used when the list has terms occurring in order of increasing size!

# Example

Search for 19 in the following list

[ 1, 2, 3, 5, 6, 7, 8, 10, 12, 13, 15, 16, 18, 19, 20, 22 ];

1. Split this list into two smaller lists with eight terms each:
   list_left = [ 1, 2, 3, 5, 6, 7, 8, 10 ]
   list_right = [ 12, 13, 15, 16, 18, 19, 20, 22 ]
2. Largest term in list_left: 10
   10 < 19, so the search for 19 can be restricted to the list containing the 9th through the 16th terms of the original list.
3. Split list_right:
   list_left = [ 12, 13, 15, 16 ]
   list_right = [ 18, 19, 20, 22 ]
4. Largest term in list_left: 16
   16 < 19, so list_right can be considered only.
5. Split list_right:
   list_left = [ 18, 19 ]
   list_right = [ 20, 22 ]
6. Because 19 of list_list is not greater than the target value 19, the search is restricted to list_left
7. Split list_left:
   list_left = [ 18 ]
   list_right = [ 19 ]
8. 18 < 19, so the search is restricted to list_right.
9. Now the search has been narrowed down to one term and 19 is located as the 14th term in the original list.

# Pseudocode

arr: array
x: target integer
a1, a2, ... , an: increasing intergers stored in an array
m: midpoint

procedure()
    i := 1
    j := arr.size()
    while i is less than j do:
    	m := floor((i + j) / 2)
        if x is greater than am
        	i := m + 1
        else
        	j := m
    end while

/* if x is found */
if x is equal to ai
	location := i
/* if x is not found */
else
	location := 0
return location