How to differentiate recursive and non recursive difference equations?

When the derived variable is a function of either the same variable with delay(s) in the time dimension with or without combination of different variables which are simple (and)(or)compund (and)(or) complex functions, then its rightly recursive equation. In simple words present variable is a dependent of its past.Again recursive equations have infinite sequence when the time tends to infinity.

When the derived variable is independent of the past value of the derived variable involving simple (and)(or)compund (and)(or) complex functions, then its nonrecursive equation.

example:

y(t)=0.5y(t-1)+2x(t) ----recursive equation.

y(t)=3x(t)----------------nonrecursive equation.

where y and x are variables in time dimension t.

 

Recursive function is nothing but function within function. It contains some multiple functions.

One of Pythagoras's major contributions to this topic was his idea of triangular numbers.  Triangular numbers are formed by the equation where tn is the nth triangular number:

 tn = tn-1 + n                 = tn-2 + (n-1) + n                                  = t1 + 2 + 3 + ... + (n-1) + n                                  = 1 + 2 + 3 + ... + (n-1) + n

This formula tells us we can calculate triangular numbers by adding up consecutive numbers.  For example, the ninth triangular number is equal to:

                                               t9 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 t9 = 45

There is a useful shortcut that can be used to find a large triangular number.  If you want to find the 1000 triangular number, you could add up all the numbers from 1 to 1000.  Or you could use this simpler method:

tn= (n2 +n) ÷ 2

So the 1000th triangular number is:

                  t1000 = (10002 + 1000) ÷ 2 t1000 = 500500

Pythagoras's triangular numbers got that name because that is what you can visualize them as.  Each one, when arranged started at t1 = 1, the first triangular number, will form a equilateral triangle.  The first four triangular numbers would look like the following:

• A recursive function in general has an extremely high time complexity while a non-recursive one does not.
• A recursive function generally has smaller code size whereas a non-recursive one is larger.
• In some situations, only a recursive function can perform a specific task, but in other situations, both a recursive function and a non-recursive one can do it.

Here is a recursive version of calculating the Fibonacci number: 

1 /* compute n’th Fibonacci number by using recursion */ 2 int fibonacci(int n){ 3     if(n<=2) 4         return 1; 5     else 6         return fibonacci(n-1) + fibonacci(n-2); 7 }

An experienced programmer should have no problem understanding the logic behind the code. As we can see, in order to compute a Fibonacci number, Fn, the function needs to call Fn-1 and Fn-2. Fn-1 recursively calls Fn-2 and Fn-3, and Fn-2 calls Fn-3 and Fn-4. In a nutshell, each call recursively computes two values needed to get the result until control hits the base case, which happens when n<=2. You can write a simple main() that accepts an integer n as input and outputs the n’th Fibonacci by calling this recursive function and see for yourself how slowly it computes as n gets bigger. It gets horrendously slow once n gets past 40 on my machine. Here is a non-recursive version that calculates the Fibonacci number: 

01 /* compute n’th Fibonacci number by using a loop */ 02 int fibonacci(int n){ 03     if(n<=2) 04         return 1; 05     int i, last, nextToLast, result; 06     last = 1; 07     nextToLast = 1; 08     result = 1; 09     for(i=3; i<=n; i++){ 10         result = last + nextToLast; 11         nextToLast = last; 12         last = result; 13     } 14     return result; 15 }

The logic here is to keep the values already computed in variables last andnextToLast in every iteration of the for loop so that every Fibonacci number is computed exactly once. In this case, every single value is computed only once no matter how big n is. Try to replace the recursive version with this version and see how fast you get the result when n is very big. By analyzing these examples, we should have no problem seeing that recursion usually has small code size, but sometimes the price it pays in the execution time is far too dear.