Recursivity is a method of defining and calculating the functions that call themselves. A recursive sequence is characterized by each of its elements, by its first value and by the recursive relation that is used to determine a general element of the sequence.

Example: the sequence {u[1]...u[n]}

u[1]=1;

u[n]=u[n-1]+1.

Here are some famous recursive functions:

1. Ackermann:

ac(m,n)=

- n+1, if m=0

- ac(m-1,1), if n=0

- ac(m-1,ac(m,n-1)), otherwise

2. Fibonacci:

fib(n)=

- 1, if n=0 or n=1

- fib(n-1)+fib(n-2), if n>=2

3. Sterling:

st(i,j)=st[i-1,j-1]+ j*st[i-1,j]

This function is used for determining the number of ways of giving n prices to m people so that everybody gets at least a price.

 

Here are the programs for determining fibonacci(n):

Pascal program:

var i,j,k,n:longint;

function fibonacci(n:integer):integer;
begin
if (n=0) or (n=1) then fibonacci:=1
else fibonacci:=fibonacci(n-2)+fibonacci(n-1);
end;

begin
readln(n);
writeln(fibonacci(n));
end.

C++ program:

#include<iostream.h>
int n;

int fibonacci(int n)
{
int k,l;
if ((n==0)||(n==1)) {return(1);}
else {return(fibonacci(n-2)+fibonacci(n-1));}
}

void main()
{
cin>>n;
cout<<fibonacci(n);
}