SPOJ FIBTWIST

SPOJ: 11409. Fibonacci With a Twist

After passing hours on it, finally I was able to solve it. Problem statement is pretty clear, given a recursive function, find its nth term.

f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2) + (n-1)

The given range on n makes it obvious that this solution must have a logarithmic algorithm or constant close form. However, I don't know about the close form, mathematics was not my thing. I am also not sure if this can be solved directly using matrix exponentiation.

Looking at the recurrence, it is obvious that the equation can be written in the following form for higher n:

f(n) = a_nf(0) + b_nf(1) + c_n

Here, a_n, b_n and c_n are coefficients for nth term. We can also discard all the terms containing f(0) which is actually 0. So, if we continue writing this, we can find a really nice pattern:

f(0) = 0
f(1) = 1
f(2) = f(1) + (2-1) = 1 + (1)
f(3) = f(2) + f(1) + (3-1) = 2 + (1) + (2)
f(4) = f(3) + f(2) + (4-1) = 3 + 2(1) + (2) + (3)

similarly...
f(5) = 5 + 3(1) + 2(2) + (3) + (4)
f(6) = 8 + 5(1) + 3(2) + 2(3) + (4) + (5)
f(7) = 13 + 8(1) + 5(2) + 3(3) + 2(4) + (5) + (6)
f(8) = 21 + 13(1) + 8(2) + 5(3) + 3(4) + 2(5) + (6) + (7)

I think some Fibonacci numbers caught our eyes already. So, now we try to generalize. Just to note: we can do this because the coefficients of similar terms are consecutive fibonacci numbers.
f(n) = fib(n) + fib(n-1)*1 + fib(n-2)*2 + fib(n-3)*3 + ... ... + fib(1)*(n-1)
f(n+1) = fib(n+1) + fib(n)*1 + fib(n-1)*2 + fib(n-2)*3 + ... ... + fib(1) * n

subtracting f(n) from f(n+1), we can get:
f(n+1)-f(n) = fib(n+1) + {fib(n-1) + ... ... + fib(1)}
f(n+1)-f(n) = fib(n+1) + fib(n+1) - 1 [sum(fib(n)) = fib(n+2)-1]
f(n+1) = f(n) + 2fib(n+1) - 1

This can be solved directly using matrix exponentiation. However, we will need a 4x4 matrix to do that. But, we can actually reduce this equation to a non recursive version:

f(n+1) = f(n) + 2fib(n+1) - 1
f(n+1) = f(n-1) 2fib(n) + 2fib(n+1) - 2
f(n+1) = f(n-2) + 2fib(n-1) + 2fib(n) + 2fib(n+1) - 3
f(n+1) = f(0) + 2fib(1) + 2fib(2) + 2fib(3) + ... ... + 2fib(n+1) - (n+1)
f(n+1) = 2(fib(n+3) - 1) - (n+1)

So, rewriting for f(n):
f(n) = 2(fib(n+2) - 1) - n

Now, this is no more a hard recursive function, we just need to know (n+2)th fibonacci term, which can be computed using only a 2x2 matrix. This post shows you how, if you need to know.

However, for this specific problem, be careful about the final result, you may need modulus correction.

Matrix Exponentiation

Introduction:

Don't be confused with the title, this article has nothing to do with "how to calculate an exponent of a given matrix", rather it will discuss on how to use this technique to solve a specific class of problems.

Sometimes we face some problems, where, we can easily derive a recursive relation (mostly suitable for dynamic programming approach), but the given constraints make us about to cry, there comes the matrix exponentiation idea. The situation can be made more clear with the following example:

Let, a problem says: find f(n) : n'th Fibonacci number. When n is sufficiently small, we can solve the problem with a simple recursion, f(n) = f(n-1) + f(n-2), or, we can follow dynamic programming approach to avoid the calculation of same function over and over again. But, what will you do if the problem says, given 0 < n < 1000000000, find f(n) % 999983 ? No doubt dynamic programming will fail!

We'll develop the idea on how and why these types of problems could be solved by matrix exponentiation later, first lets see how matrix exponentiation can help is to represent recurrence relations.

Prerequisite:

Before continuing, you need to know:

• Given two matrices, how to find their product, or given the product matrix of two matrices, and one of them, how to find the other matrix.
• Given a matrix of size d x d, how to find its n'th power in O( d³log(n) ).

Patterns:

What we need first, is a recursive relation, and what we want to do, is to find a matrix M which can lead us to the desired state from a set of already known states. Let, we know k states of a given recurrence relation, and want to find the (k+1)th state. Let M be a k x k matrix, and we build a matrix A:[k x 1] matrix from the known states of the recurrence relation, now we want to get a matrix B:[k x 1] which will represent the set of next states, i.e. M x A = B, as shown below:

| f(n) | | f(n+1) | | f(n-1) | | f(n) | M x | f(n-2) | = | f(n-1) | | ...... | | ...... | | f(n-k) | |f(n-k+1)|

So, if we can design M accordingly, job's done!, the matrix will then be used to represent the recurrence relation.

• Type 1:

  Lets start by the simplest one, f(n) = f(n-1) + f(n-2).
  So, f(n+1) = f(n) + f(n-1)
  Let, we know, f(n) and f(n-1); we want to get f(n+1)
  From the above situation, matrix A and B can be formed as shown below:
  

  
  
  
  
  

  Matrix A	Matrix B
  | f(n) | | f(n-1) |	| f(n+1) | | f(n) |

  
  [Note: matrix A will be always designed in such a way that, every state on which f(n+1) depends, will be present]
  So, now, we need to design a 2x2 matrix M such that, it satisfies M x A = B as stated above.
  The first element of B is f(n+1) which is actually f(n) + f(n-1). To get this, from matrix A, we need, 1 f(n) and 1 f(n-1). So, the 1st row of M will be [1 1].
  

  | 1 1 | x | f(n) | = | f(n+1) | | ----- | | f(n-1) | | ------ |

  
  [Note: ----- means, we are not concerned about this value]
  Similarly, 2nd item of B is f(n) which we can get by simply taking 1 f(n) from A. So, the 2nd row of M is [1 0].
  

  | ----- | x | f(n) | = | ------ | | 1 0 | | f(n-1) | | f(n) |

  
  [I hope you know how a matrix multiplication is done and how the values ar assigned!]
  Thus we get the desired 2 x 2 matrix M:
  

  | 1 1 | x | f(n) | = | f(n+1) | | 1 0 | | f(n-1) | | f(n) |

  
  

  If you are confused about how the above matrix is calculated, you might try doing it this way:

  
  

  We know, the multiplication of an n x n matrix M with an n x 1 matrix A will generate an n x 1 matrix B, i.e. M x A = B. The k'th element in the product matrix B is the product of k'th row of the n x n matrix M with the n x 1 matrix A in the left side.
  In the above example, the 1st element in B is f(n+1) = f(n) + f(n-1). So, it's the product of 1st row of matrix M and matrix B. Let, the first row of M is [x y]. So, according to matrix multiplication,
  

  
   x * f(n) + y * f(n-1) = f(n+1) = f(n) + f(n-1)
  ⇒ x = 1, y = 1
  

  
  Thus we can find the first row of matrix M is [1 1]. Similarly, let, the 2nd row of matrix M is [x y], and according to matrix multiplication:
  

  
   x * f(n) + y * f(n-1) = f(n)
  ⇒ x = 1, y = 0
  

  
  Thus we get the second row of M is [1 0].
  

• Type 2:

  Now, we make it a bit complex: find f(n) = a * f(n-1) + b * f(n-2), where a, b are some constants.
  This tells us, f(n+1) = a * f(n) + b * f(n-1).
  By this far, this should be clear that the dimension of the matrices will be equal to the number of dependencies, i.e. in this particular example, again 2. So, for A and B, we can build two matrices of size 2 x 1:
  

  
  
  
  
  

  Matrix A	Matrix B
  | f(n) | | f(n-1) |	| f(n+1) | | f(n) |

  
  Now for f(n+1) = a * f(n) + b * f(n-1), we need [a b] in the first row of objective matrix M instead of [1 1] from the previous example. Because, now we need a of f(n)'s and b of f(n-1)'s.
  

  | a b | x | f(n) | = | f(n+1) | | ----- | | f(n-1) | | ------ |

  
  And, for the 2nd item in B i.e. f(n), we already have that in matrix A, so we just take that, which leads, the 2nd row of the matrix M will be [1 0] as the previous one.
  

  | ----- | x | f(n) | = | ------ | | 1 0 | | f(n-1) | | f(n) |

  
  So, this time we get:
  

  | a b | x | f(n) | = | f(n+1) | | 1 0 | | f(n-1) | | f(n) |

  
  Pretty simple as the previous one...




• Type 3:

  We've already grown much older, now lets face a bit complex relation: find f(n) = a * f(n-1) + c * f(n-3).
  Ooops! a few minutes ago, all we saw were contiguous states, but here, the state f(n-2) is missing. Now? what to do?

  
  

  Actually, this is not a problem anymore, we can convert the relation as follows: f(n) = a * f(n-1) + 0 * f(n-2) + c * f(n-3), deducing f(n+1) = a * f(n) + 0 * f(n-1) + c * f(n-2). Now, we see that, this is actually a form described in Type 2. So, here, the objective matrix M will be 3 x 3, and the elements are:
  

  | a 0 c | | f(n) | | f(n+1) | | 1 0 0 | x | f(n-1) | = | f(n) | | 0 1 0 | | f(n-2) | | f(n-1) |

  
  These are calculated in the same way as Type 2. [Note, if you find it difficult, try on pen and paper!]
  




• Type 4:

  Life is getting complex as hell, and Mr. problem now asks you to find f(n) = f(n-1) + f(n-2) + c where c is any constant.

  
  

  Now, this is a new one and all we have seen in past, after the multiplication, each state in A transforms to its next state in B.
  f(n) = f(n-1) + f(n-2) + c
  f(n+1) = f(n) + f(n-1) + c
  f(n+2) = f(n+1) + f(n) + c
  ................................. so on
  So, normally we can't get it through the previous fashions. But, how about now we add c as a state?
  

  | f(n) | | f(n+1) | M x | f(n-1) | = | f(n) | | c | | c |

  
  Now, its not much hard to design M according to the previous fashion. Here it is done, but don't forget to verify on yours:
  

  | 1 1 1 | | f(n) | | f(n+1) | | 1 0 0 | x | f(n-1) | = | f(n) | | 0 0 1 | | c | | c |




• Type 5:

  Lets put it altogether: find matrix suitable for f(n) = a * f(n-1) + c * f(n-3) + d * f(n-4) + e.
  I would leave it as an exercise to reader. The final matrix is given here, check if it matches with your solution. Also find matrix A and B.
  

  | a 0 c d 1 | | 1 0 0 0 0 | | 0 1 0 0 0 | | 0 0 1 0 0 | | 0 0 0 0 1 |

  
  [Note: you may take a look back to Type 3 and 4]
  

• 
  

  Type 6:

  
  

  
  Sometimes, a recurrence is given like this:
  

  
  f(n) = if n is odd, f(n-1) else, f(n-2)
  In short:
  f(n) = (n&1) * f(n-1) + (!(n&1)) * f(n-2)
  

  
  Here, we can just split the functions in the basis of odd even and keep 2 different matrix for both of them and calculate separately. Actually, there might appear many different patterns, but these are the basic patterns.
  




• Type 7:

  Sometimes we may need to maintain more than one recurrence, where they are interrelated. For example, let a recurrence relation be:
  g(n) = 2g(n-1) + 2g(n-2) + f(n), where, f(n) = 2f(n-1) + 2f(n-2). Here, recurrence g(n) is dependent upon f(n) and the can be calculated in the same matrix but of increased dimensions. Lets design the matrices A, B then we'll try to find matrix M.

  
  
  
  

  Matrix A	Matrix B
  | g(n) | | g(n-1) | | f(n+1) | | f(n) |	| g(n+1) | | g(n) | | f(n+2) | | f(n+1) |

  
  Here, g(n+1) = 2g(n) + 2g(n-1) + f(n+1) and f(n+2) = 2f(n+1) + 2f(n).
  Now, using the above process, we can generate the objective matrix M as follows:
  

  | 2 2 1 0 | | 1 0 0 0 | | 0 0 2 2 | | 0 0 1 0 |

So, these are the basic categories of recurrence relations which are used to be solved by this simple technique.

Analysis:

Now that we have seen how matrix multiplication can be used to maintain recurrence relations, we are back to out first question, how this helps us in solving recurrences on a huge range.

Recall the recurrence f(n) = f(n-1) + f(n-2).
We already know that:

M x | f(n) | = | f(n+1) | | f(n-1) | | f(n) |

............(1)

How about we multiply M multiple times? Like this:

M x M x | f(n) | = | f(n+1) | | f(n-1) | | f(n) |

Replacing from (1):

M x M x | f(n) | = M x | f(n+1) | = | f(n+2) | | f(n-1) | | f(n) | | f(n+1) |

So, we finally get:

M^2 x | f(n) | = | f(n+2) | | f(n-1) | | f(n+1) |

Similarly we can show:

M^3 x | f(n) | = | f(n+3) | | f(n-1) | | f(n+2) |

M^4 x | f(n) | = | f(n+4) | | f(n-1) | | f(n+3) |

............................... ............................... ...............................

M^k x | f(n) | = | f(n+k) | | f(n-1) | |f(n+k-1)|

Thus we can get any state f(n) by simply raising the power of objective matrix M to n-1 in O( d³log(n) ), where d is the dimension of square matrix M. So, even if n = 1000000000, still this can be calculated pretty easily as long as d³ is sufficiently small.

Related problems:

UVa 10229 : Modular Fibonacci
UVa 10870 : Recurrences
UVa 11651 : Krypton Number System
UVa 10754 : Fantastic Sequence
UVa 11551 : Experienced Endeavour

Regards, Zobayer Hasan.

Threaded Merge Sort

What?

In my previous post about Merge Sort, the algorithm for merge sort was discussed. Although the pictures shows something which appears to be apparently parallel, but actually they are not. In fact, as the procedure introduced there was recursive, it works in a post-order fashion, meaning, first it solves the left half, then the right half, and then it works with the current range. The following picture shows the actual work-flow of the standard recursive merge sort algorithm:


The red lines and numbers shows the actual call sequence of the algorithm merge sort, for reference, the basic algorithm, is shown here again:

MERGE-SORT(A, p, r):
    if p < r
        then q := (r + p) / 2
        MERGE-SORT(A, p, q)
        MERGE-SORT(A, q+1, r)
        MERGE(A, p, q, r)

So, from the above example, we can see that no two calls are concurrent, i.e. parallel. Each call is one of the three calls made in MERGE-SORT(A, p, r) procedure stated above, also shown below (according to the picture, p=0, r=6):

Step-00: MERGE-SORT(A, 0, 6)
Step-01: MERGE-SORT(A, 0, 3)
Step-02: MERGE-SORT(A, 0, 1)
Step-03: MERGE-SORT(A, 0, 0)
Step-04: MERGE-SORT(A, 1, 1)
Step-05: MERGE(A, 0, 0, 1)
Step-06: MERGE-SORT(A, 2, 3)
Step-07: MERGE-SORT(A, 2, 2)
Step-08: MERGE-SORT(A, 3, 3)
Step-09: MERGE(A, 2, 2, 3)
Step-10: MERGE(A, 0, 1, 3)
Step-11: MERGE-SORT(A, 4, 6)
Step-12: MERGE-SORT(A, 4, 5)
Step-13: MERGE-SORT(A, 4, 4)
Step-14: MERGE-SORT(A, 5, 5)
Step-15: MERGE(A, 4, 4, 5)
Step-16: MERGE-SORT(A, 6, 6)
Step-17: MERGE(A, 4, 5, 6)
Step-18: MERGE(A, 0, 3, 6)

Also note that, there are no overlapping calls at a same level of the tree, which is going to be a key factor.

How threading helps:

After a few observations, we can easily find out some interesting properties about merge sort algorithm. If we closely look at the merge sort tree structure, it becomes very clear that, int the recursive call tree, parent nodes depend on children, but siblings are independent. This property helps us to deduce a threaded version of merge sort algorithm where, we can really solve the left and right sub-portion of a range in a parallel fashion by making the calls threaded.

As the algorithm here is recursive, it might look confusing at the first glance, but it is not. Because, nodes share data only with their ancestors and in a call, we can wait until the threads finish their works. So, no concurrency problem appears here. Also, we don't need to worry about mutual exclusion of the shared data, because, there is no such situation in this algorithm, already stated above.

So, the threaded version of the algorithm will look like this:

THREADED-MERGE-SORT(A, p, r):
    if p < r
        then q := (r + p) / 2
        start_thread(left_thread, THREADED-MERGE-SORT(A, p, q))
        start_thread(right_thread, THREADED-MERGE-SORT(A, q+1, r))
        wait_for(left_thread)
        wait_for(right_thread)
        MERGE(A, p, q, r)

According to the above algorithm, the flow of program changes which is shown in the picture below:


Now because of being able to run multiple THREADED-MERGE-SORT() at a time, and the job scheduling features of modern computers, the effective number of iteration is dramatically reduced, resulting a much much elegant solution for the heavy duty areas like manipulating large data on drives.

A simple implementation:

Here a simple implementation is presented using pthread library in C++:

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

typedef struct { int i, j; } pair;
const int MAX = 1024;
int a[MAX];
pthread_attr_t attr;

void *threaded_merge_sort(void *param) {
    pair range = *(pair *)param, lrange, rrange;
    pthread_t lside, rside;
    int p = range.i, q, r = range.j, n1, n2, n = r-p+1, i, j, k;
    int *aleft, *aright;
    if(p < r) {
        q = (p + r) >> 1;
        lrange.i = p, lrange.j = q, rrange.i = q + 1, rrange.j = r;
        pthread_create(&lside, &attr, threaded_merge_sort, (void *)&lrange);
        pthread_create(&rside, &attr, threaded_merge_sort, (void *)&rrange);
        pthread_join(lside, NULL);
        pthread_join(rside, NULL);
        n1 = q - p + 1, n2 = r - q;
        aleft = (int *)malloc(sizeof(int) * n1);
        aright = (int *)malloc(sizeof(int) * n2);
        for(i = 0; i < n1; i++) aleft[i] = a[p+i];
        for(i = 0; i < n2; i++) aright[i] = a[q+1+i];
        for(k = i = j = 0; k < n; k++) {
            if(i >= n1 || (j < n2 && aleft[i] > aright[j])) a[k+p] = aright[j++];
            else a[k+p] = aleft[i++];
        }
        free(aleft);
        free(aright);
    }
    return NULL;
}

int main() {
    int n, i;
    pthread_t sorter;
    pair range;
    pthread_attr_init(&attr);
    pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);
    while(scanf("%d", &n)==1 && n) {
        for(i = 0; i < n; i++) scanf("%d", &a[i]);
        range.i = 0, range.j = n-1;
        pthread_create(&sorter, &attr, threaded_merge_sort, (void *)&range);
        pthread_join(sorter, NULL);
        for(i = 0; i < n; i++) printf("%d%c", a[i], (i==n-1? '\n' : ' '));
    }
    pthread_attr_destroy(&attr);
    return 0;
}

This may look a bit messy, but, actually, you may find a little difference with the original one, we just created threads instead of plain recursive calls, that's it.
To learn more about pthread, check these out:

• https://computing.llnl.gov/tutorials/pthreads/
• http://www.yolinux.com/TUTORIALS/LinuxTutorialPosixThreads.html
• http://sourceware.org/pthreads-win32/

Give it a try! :)

Power Series Evaluation

Power series evaluation in O(lg(n)):[n is the number of terms]

We'll try to evaluate the following power series in logarithmic time w.r.t. the number of terms n.


Well well... I may be asked, "dude, why do you want to do this in O(lg(n)) when there's already we have a O(1) solution for your problem?". Answer is simple, "I'm trying it from a programming perspective and the O(1) can get sometimes impossible when n keeps going up i.e. like 10¹⁰⁰⁰ and you are asked to return the answer w.r.t. some %m [modulus m] (meaning the final result will not reach m). This method will be suitable for this case only. Because, calculating {(x^n-1-1)/(x-1)}%m is not a very easy task and sometimes, it is not directly possible.

This series can be evaluated by binary splitting and recursively solving those building up the answer.
Let n = 6
We have, 1 + x + x² + x³ + x⁴ + x⁵
⇒ (1 + x + x²) + x³(1 + x + x²)
⇒ (1 + x + x²)(1 + x³)

So, when n is even, f(x, n) = (1 + x^n/2)f(x, n/2)

Now, what if n is odd, Let n = 7
We have, 1 + x + x² + x³ + x⁴ + x⁵ + x⁶
⇒ (1 + x + x²) + x³(1 + x + x²) + x⁶
⇒ (1 + x + x²)(1 + x³) + x⁶

So, when n is odd, f(x, n) = (1 + x^n/2)f(x, n/2) + x^n-1

So, by combining the above 2 equations, we get the final solution:
f(x, n) = (1 + x^n/2)f(x, n/2) + (n%2)x^n-1

By some clever observation, the need for -1 and %2 operation on n can be eliminated. So, the only thing we need to do is the /2 operation on n, which is easy even when n is a big integer.

Here is a python module that shows only the recursive part, no trick applied.

import math

def evaluate(x, n):
    if(n==0):
        return 0
    if(n==1):
        return 1
    ret = 0
    if(n%2==1):
        ret = ret + int(math.pow(x, n-1))
    n = n/2
    return ret + evaluate(x, n)*(1 + int(math.pow(x, n)))

If this is to be done with C/C++, some biginteger division algorithm should be implemented.

Easy, eh? Check different types of series here

Attacking Recursions

Some general approach for solving recursive problems:

If anyone want to read an awesome super cool tutorial on recursion in BANGLA... read from Fahim Vai's page

#1: Forget about what you need to do, just think about any input, for which you know what your function should output, as you know this step, you can build up a solution for your problem. Suppose you have a function which solves a task, and you know, this task is somehow related to another similar task. So you just keep calling that function again and again thinking that, the function I'm calling will solve the problem anyhow, and the function will also say, I'll solve this problem, if you give me the result for another sub-problem first!!! Well, then you'll say, "So, why don't you use your twin-brother to solve that part?" and so on... The following example will show you how to start writing a recursive function.

Example: Think about computing n! recursively. I still don't know what and how my function will do this. And I also don't know, like what could be 5! or 7!... But nothing to worry about, I know that 0! = 1! = 1. And I also know that, n! = n(n-1)!. So I will think like that, "I will get n! from a function F, if some one gives me (n-1)!, then I'll multiply it with n and produce results". And, thus, F is the function for computing n!, so why don't I use again to get (n-1)! ? And when F tries to find out what could be the value of (n-1)!, it also stumbles at the same point, it wonders what would be the value of (n-2)!... then we tell him to use F again to get this... and this thing keeps going as long as we don't know what F actually should return for any k. In case of k = 1, as we know now F can return 1 for k = 1, and it don't need to call another F to solve anything first...

int factorial(int n) {
    // I know this, so I don't want my function to go any further...
    if(n==0) return 1;
    // don't bother what to do, just reuse the function...
    else return n*factorial(n-1);
}

#2: What ever you can do with loops, can be done with recursions as well. A simple technique for converting recursions and loops is shown below:

Forward:
for loop:

for(int i = 0; i < n; i++) {
    // do whatever needed
}

Equivalent recursion:

void FOR(int i, int n) {
    if(i==n) return; // terminates
    // do whatever needed
    FOR(i+1, n); // go to next step
}

Backward:
for loop:

for(int i = n-1; i >= 0; i -= 1) {
    // do whatever needed
}

Equivalent recursion:

void ROF(int i, int n) {
    if(i==n) return; // terminates
    ROF(i+1, n); // keep going to the last
    // do whatever needed when returning from prev steps
}

Well, you may wonder how this is backward loop? But just think of its execution cycle, just after entering the function, it is calling itself again incrementing the value of i, and the execution routine that you have written under the function call, was paused there. From the new function it enters, it works the same way, call itself again before executing anything...Thus when you have reached the limiting condition, or the base condition, then the function stops recursion and starts returning, and the whole process can be shown as below...let n=5, and we want to print 5 4 3 2 1...code for this might be:

void function(int i, int n) {
    if(i<=n) {
        function(i+1, n);
        printf("%d ", i);
    }
}

Explanation might look like this:

01|call function1 with i=1
02|    call function2 with i=2
03|        call function3 with i=3
04|            call function4 with i=4
05|                call function5 with i=5
06|                    call function6 with i=6
07|                        i breaks condition, no more calls
08|                    return to function5
09|                    print 5
10|                return to function4
11|                print 4
12|            return to function3
13|            print 3
14|        return to function2
15|        print 2
16|    return to function1
17|    print 1
18|return to main, done!

Left side number shows the execution steps, so from the above program, we get, 5 4 3 2 1. So indeed it ran on reverse direction...

#3: Use the advantage of call stack. When you call functions recursively, it stays in the memory as the following picture demonstrates.

int f(int n) {
    if(n==0) return 1;
    return n*f(n-1);
}

You know about stack, in a stack, you cannot remove any item unless it is the topmost. So you can consider the calling of a recursive function as a stack, where, you can't remove the memory used by f(n=3) before removing f(n=2) and so so... So, you can easily see that, the functions will hold all their variables and values until it is released. This actually serves the purpose of using an array.

#4: Be careful while using recursions. From a programming contest aspects, recursions are always best to avoid. As you've seen above, most recursions can be done using loops somehow. Recursions have a great deal of drawbacks and it most of the time extends the execution time of your program. Though recursions are very very easy to understand and they are like the first idea in many problems that pops out in mind first... they still bear the risks of exceeding memory and time limits.



Generally, in loops, all the variables are loaded at the same time which causes it a very low memory consumption and faster access to the instructions. But whenever we use recursions, each function is allotted a space at the moment it is called which requires much more time and all the internal piece of codes stored again which keeps the memory consumption rising up. As your compiler allows you a specific amount of memory (generally 32 MB) to use, you may overrun the stack limit by excessive recursive calls which causes a Stack Overflow error (a Runtime Error).



So, please think a while before writing recursions whether your program is capable of running under the imposed time and memory constraints. Generally recursions in O(lg n) are safe to use, also we may go to a O(n) recursion if n is pretty small.

#5: If the recursion tree has some overlapping branches, most of the times, what we do, is to store already computed values, so, when we meet any function which was called before, we may stop branching again and use previously computed values, which is a common technique knows as Dynamic Programming (DP), we will talk about that later as that is pretty advanced.

These techniques will be used in almost all problems when writing recursive solution. Just don't forget the definition of recursion:
Definition of recursion = See the Definition of recursion

Now try this

Practice Recursions

Recursions are fun

You may like to try out some simple problems to practice recursions. Try to solve all of them without using any global variables. And try on your own before looking at the solutions. Also please notify any error to me ( zobayer1[at]gmail[dot]com ). Before looking at the problems, you may like to read this post about how to attack recursive problems.

Problem 1:

You will be given an array of integers, write a recursive solution to print it in reverse order.

Input:
5
69 87 45 21 47
Output:
47 21 45 87 69

see answer

Problem 2:

Write a recursive function to print an array in the following order. [0] [n-1] [1] [n-2] ......... ......... [(n-1)/2] [n/2]

Input:
5
1 5 7 8 9
Output:
1 9
5 8
7 7

see answer

Problem 3:

Write a recursive program to remove all odd integers from an array. You must not use any extra array or print anything in the function. Just read input, call the recursive function, then print the array in main().

Input:
6
1 54 88 6 55 7
Output:
54 88 6

see answer

Problem 4:

Write a recursive solution to print the polynomial series for any input n: 1 + x + x² + ................. + x^n-1

Input:
5
Output:
1 + x + x^2 + x^3 + x^4

see answer

Problem 5:

Write a recursive solution to evaluate the previous polynomial for any given x and n. Like, when x=2 and n=5, we have 1 + x + x² + ................. + x^n-1 = 31

Input:
2 5
Output:
31

see answer

Problem 6:

Write a recursive program to compute n!

Input:
5
Output:
120

see answer

Problem 7:

Write a recursive program to compute n^th fibonacci number. 1^st and 2^nd fibonacci numbers are 1, 1.

Input:
6
Output:
8

see answer

Problem 8:

Write a recursive program to determine whether a given integer is prime or not.

Input:
49
999983
1
Output:
not prime
prime
not prime

see answer

Problem 9:

Write a recursive function that finds the gcd of two non-negative integers.

Input:
25 8895
Output:
5

see answer

Problem 10:

Write a recursive solution to compute lcm of two integers. You must not use the formula lcm(a,b) = (a x b) / gcd(a,b); find lcm from scratch...

Input:
23 488
Output:
11224

see answer

Problem 11:

Suppose you are given an array of integers in an arbitrary order. Write a recursive solution to find the maximum element from the array.

Input:
5
7 4 9 6 2
Output:
9

see answer

Problem 12:

Write a recursive solution to find the second maximum number from a given set of integers.

Input:
5
5 8 7 9 3
Output:
8

see answer

Problem 13:

Implement linear search recursively, i.e. given an array of integers, find a specific value from it. Input format: first n, the number of elements. Then n integers. Then, q, number of query, then q integers. Output format: for each of the q integers, print its index (within 0 to n-1) in the array or print 'not found', whichever is appropriate.

Input:
5
2 9 4 7 6
2
5 9
Output:
not found
1

see answer

Problem 14:

Implement binary search recursively, i.e. given an array of sorted integers, find a query integer from it. Input format: first n, the number of elements. Then n integers. Then, q, number of query, then q integers. Output format: for each of the q integers, print its index (within 0 to n-1) in the array or print 'not found', whichever is appropriate.

Input:
5
1 2 3 4 5
2
3 -5
Output:
2
not found

see answer

Problem 15:

Write a recursive solution to get the reverse of a given integer. Function must return an int

Input:
123405
Output:
504321

see answer

Problem 16:

Read a string from keyboard and print it in reversed order. You must not use any array to store the characters. Write a recursive solutions to solve this problem.

Input:
helloo
Output:
oolleh

see answer

Problem 17:

Write a recursive program that determines whether a given sentence is palindromic or not just considering the alpha-numeric characters ('a'-'z'), ('A'-'Z'), ('0'-'9').

Input:
madam, i'm adam
hulala
Output:
palindromic
not palindromic

see answer

Problem 18:

Implement strcat(), stracpy(), strcmp() and strlen() recursively.

Input:
test on your own
Output:
test on your own

see answer

Problem 19:

If you already solved the problem for finding the n^th fibonacci number, then you must have a clear vision on how the program flow works. So now, in this problem, print the values of your fibonacci function in pre-order, in-order and post-order traversal. For example, when n = 5, your program calls 3 and 4 from it, from the call of 3, your program calls 1 and 2 again....... here is the picture:

Input:
5
Output:
Inorder: 1 3 2 5 2 4 1 3 2
Preorder: 5 3 1 2 4 2 3 1 2
Postorder: 1 2 3 2 1 2 3 4 5

see answer

Problem 20:

All of you have seen the tower of Hanoi. You have 3 pillars 'a', 'b' and 'c', and you need transfer all disks from one pillar to another. Conditions are, only one disk at a time is movable, and you can never place a larger disk over a smaller one. Write a recursive solution to print the moves that simulates the task, a -> b means move the topmost of tower a to tower b.

Input:
3
Output:
a -> c
a -> b
c -> b
a -> c
b -> a
b -> c
a -> c

see answer

Good Luck!!!