Skip to content

Recursive Algorithm

Like Recurrence Relations, recursive algorithms, are algorithms that have a cycle in function calls

1
2
3
4
5
6
int fn(int value) {
    if(value >= 1) {
        printf("%d ", value);
        fn(value - 1);
    }
}

A recursive function can go infinite like a loop. To avoid infinite running of recursive function, there are two properties that a recursive function must have:

  1. Base criteria: Or Initial Condition, when this condition is met the function stops calling itself recursively.
  2. Progressive approach: The recursive calls should progress in such a way that each time a recursive call is made it comes closer to the base criteria.

Concepts

Call Stack

Many programming languages implement recursion by means of stacks, The caller calls the callee in form of transfering execution control to the callee with passing Input Data, these datas will save in a new Stack Frame (Activation Record) then the callee will access them

  • Activation record of each call contains:
    • Input params
    • Output space
    • Return address
    • etc

Activation Record

Call Tree

Recursion functions will call each other, we can draw a tree of function calls, by traversing that tree we can find the order of function calls

Call Tree

  • Example: Write the correct sequence of numbers which will be printed by calling fn(4):
1
2
3
4
5
6
7
8
const fn = (n) => {
    if (n > 1) {
        fn(n - 1);
        console.log(n + 2);
        fn(n - 2);
        console.log(n + 3);
    }
};

Call Tree Example

Analysis

In most cases the Space Complexity and Time Complexity of an Iterative Algorithm is better than it's Recursive Version

For analysing recursive algorithms, we must convert them into Iterative Algorithm version, then analyse it and find the Time Complexity and Space Complexity of them

There are two main types of analysis for Recursive Algorithms:

  1. Call Analysis: Finding recurrence relation for number of recursion calls
  2. Value Analysis: Finding recurrence relation for value of recursion
  3. Time Analysis: Finding recurrence relation for number of operations to run
    • The Time required by Recursive Algorithm is more bigger than Iterative Algorithm because of changing Branch in each call
    • The Space required by Recursive Algorithm is more bigger than Iterative Algorithm because of saving Activation Record in each call

Call Analysis

Finding a Recurrence Relation for number of recursion calls in recursive function

  • For finding the call recurrence relation we will sum:
    • Recursive Calls
    • One(Self callee called by caller)
  • Initial Conditions are One, because they only will called by caller
1
2
3
4
5
6
7
const fn = (n) => {
    if (n <= 1) {
        return n * n;
    } else {
        return fn(n - 1) + fn(n - 2) + n;
    }
};
T(n)=T(n−1)+T(n−2)+1T(1)=1T(0)=1

Now we can solve this Recurrence Relation to find the Number of Recursion Calls of fn(n)

Value Analysis

Finding a Recurrence Relation for value of recursive function

  • For finding the value recurrence relation we will write the direct function in recurrence format
  • Initial Conditions have the exact value in recursive function
1
2
3
4
5
6
7
const fn = (n) => {
    if (n <= 1) {
        return n * n;
    } else {
        return fn(n - 1) + fn(n - 2) + n;
    }
};
T(n)=T(n−1)+T(n−2)+nT(1)=1T(0)=0

Now we can solve this Recurrence Relation to find the Direct Relation of Value of fn(n)

  • Tip: Using Bottom to Top Method is better for finding the exact value of function per an input:
1
2
3
4
5
6
7
const fn = (n) => {
    if (n <= 1) {
        return n * n;
    } else {
        return fn(n - 1) + fn(n - 2) + n;
    }
};
f(4)=?f(0)=0∗0=0f(1)=1∗1=1f(2)=f(1)+f(0)+2=1+0+2=3f(3)=f(2)+f(1)+3=3+1+3=7f(4)=f(3)+f(2)+4=7+3+4⟹14

Time Analysis

Finding a Recurrence Relation for number of operations to run of recursive function

  • For finding the time recurrence relation we will sum:
    • Recursive Calls
    • Number of Operations(if, loop, add, mul, etc)
  • Initial Conditions are Number of Operations with their input
1
2
3
4
5
6
7
const fn = (n) => {
    if (n <= 1) {
        return n * n;
    } else {
        return fn(n - 1) + fn(n - 2) + n;
    }
};
Operations:∗,+,ifT(n)=T(n−1)+T(n−2)+3T(1)=2T(0)=2

Now we can solve this Recurrence Relation to find the Time Complexity of fn(n)

  • Tip: We must focus on exact number of function calls:
    • f has One recursive function call
    • g has Two recursive function call
1
2
3
4
5
6
7
const f = () => {
    return 2 * f();
};

const g = () => {
    return g() + g();
};

Examples

  • Example 1: Find the Number of calls, Value, Number of multiplies, Time needed for function below per fn(4):
1
2
3
4
5
6
7
const fn = (n) => {
    if (n <= 1) {
        return n * n;
    }

    return fn(n - 1) + fn(n - 2) + n;
};
Call:C(n)=C(n−1)+C(n−2)+1C(1)=1,C(0)=1⟹C(2)=C(1)+C(0)+1=3⟹C(3)=C(2)+C(1)+1=5⟹C(4)=C(3)+C(2)+1=9Value:F(n)=F(n−1)+F(n−2)+nF(1)=1,F(0)=0⟹F(2)=F(1)+F(0)+2=3⟹F(3)=F(2)+F(1)+3=7⟹F(4)=F(3)+F(2)+4=14Time:T(n)=T(n−1)+T(n−2)+3T(1)=2,T(0)=2⟹T(2)=T(1)+T(0)+3=7⟹T(3)=T(2)+T(1)+3=12⟹T(4)=T(3)+T(2)+3=22Multiples:M(n)=M(n−1)+M(n−2)M(1)=1,M(0)=1⟹M(2)=M(1)+M(0)=2⟹M(3)=M(2)+M(1)=3⟹M(4)=M(3)+M(2)=5

Now we can find the Time Complexity of this function using Time Recurrence Relation:

T(n)=T(n−1)+T(n−2)+3T(1)=2,T(0)=2⟹Recurrence Tree MethodT(n)∈Θ(2n)
  • Example 2: Find the Printed Stars for fn(4):
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
const fn = (n) => {
    if (n <= 1) {
        console.log("***");
    } else {
        console.log("**");
        fn(n - 1);
        console.log("*");
        fn(n - 2);
        console.log("**");
        fn(n - 1);
    }
};
S(n)=2+S(n−1)+1+S(n−2)+2+S(n−1)=2S(n−1)+S(n−2)+5S(1)=3,S(0)=3⟹S(2)=2S(1)+S(0)+5=14⟹S(3)=2S(2)+S(1)+5=36⟹S(4)=2S(3)+S(2)+5=91