Skip to main content

Recursion

Amu_Ke_Fundye

Recursion


A function that calls itself directly or indirectly is called a recursive function. The recursive factorial function uses more memory than its non-recursive counter part. Recursive function requires stack support to save the recursive function calls.
  • Recursion leads to compact
  • It is simple
  • It is easy to understand
  • It is easy to prove correct

Example-1: Factorial Recursive Function


Example-2: GCD Recursive Function

Example-3: Fibonacci Sequence Recursive Function


Example-4: Power Recursive Function (xy)

Example-5: Searching maximum value of an array with function call max(a, 0, n-1).
int mid, leftmax, rightmax;
int max (int a[], int low, int high)
{
if (low == high) return a[low];
else
{
mid = (low + high) / 2;
leftmax = max (a, low, mid);
rightmax = max (a, mid + 1, high);
if (leftmax > rightmax) return leftmax;
else return rightmax;
}
}

Example-6: Computing the sum of numbers from 1 to n
int sum (int n)
{
int s;
if (n == 0) return 0;
s = n + sum(n-1);
return s;
}

Regards 
Amrut Jagdish Gupta
Labels:

Comments

Post a Comment

Popular posts from this blog

Undecidability

Amu_Ke_Fundye Undecidability Decidable Problem If there is a Turing machine that decides the problem, called as Decidable problem. A decision problem that can be solved by an algorithm that halts on all inputs in a finite number of steps. A problem is decidable, if there is an algorithm that can answer either yes or no. A language for which membership can be decided by an algorithm that halts on all inputs in a finite number of steps. Decidable problem is also called as totally decidable problem, algorithmically solvable, recursively solvable. Undecidable Problem A problem that cannot be solved for all cases by any algorithm whatsoever. Equivalent Language cannot be recognized by a Turing machine that halts for all inputs. The following problems are undecidable problems: Halting Problem:  A halting problem is undecidable problem. There is no general method or algorithm which can solve the halting problem for all possible inputs. Emptyness Problem:...
Post a Comment
Read more

Funny Shortcut to Remember Periodic Table

Amu_Ke_Fundye Funny Shortcut to Remember Periodic Table THE PERIODIC TABLE The periodic table is a tabular display of the chemical elements, organized on the basis of their atomic number's , electron configurations, and chemical properties.In order to appreciate the general trends in chemistry and to explain the deviations of some from these general trends we need to to have good knowledge about the position of those elements in periodic table. This knowledge is also extremely important for competitive exams. So, here I present a way to memorize this using some funny easy shortcut sentences. THE FIRST 18 ELEMENTS (H He Li Be B C N O F Ne Na Mg Al Si P S Cl Ar)  H ie  He   Li es  Be cause  B oron  C an N ot  O xide  Fl orine.. N e w  Na tions  M ight  Al so  Si ng  P eaceful  S ong  Cl early  A gain  THE ...
3 comments
Read more

Sequential Logic Circuits

Amu_Ke_Fundye Sequential Logic Circuits In sequential logic circuit, the output is dependent upon the present inputs as well as the past inputs and outputs. Sequential circuit is of two types. Synchronous Sequential Circuit:  Change in input signals can affect memory elements only upon activation of clock signals. Asynchronous Sequential Circuit:  Change in input signals can affect memory elements at any instant of time. These are faster than synchronous circuit. Flip Flops: It is a one-bit memory cell which stores the 1-bit logical data (logic 0 or logic 1). It is a basic memory element. The most commonly used application of flip flops is in the implementation of a feedback circuit. As a memory relies on the feedback concept, flip flops can be used to design it. In synchronous sequential circuit, Memory elements are clocked flip flops and generally edge triggered. In asynchronous sequential circuit, Memory elements are unclocked flip flops / t...
2 comments
Read more