Today Objectives

• Introduce recursion and recursive algorithms
• Study well-known problems and solve them with recursive algorithms
• Implement examples in C/C++

Iteration

<aside> 💡 Iteration is a repetition of a mathematical or computational procedure applied to the result of a previous application.

</aside>

In programming, iteration is often referred to as looping, because when a program iterates it loops to an earlier step. Iterative approach uses for (…) or white (…) do loops to solve problems

• Example: calculate the factorial of n.
• Solution: to use a loop to run an index i from 1 to n and each iteration, we compute the factorial by multiplying the value of i.

Simple pseudo-code to calculate the factorial of an integer

factorial(n)
1: fac = 1
2: for = 1 -> n do
3:			fac = fac *i
4: end for
5: return fac

Iteration gives a lot of advantages:

• Iteration allows to simplify algorithm by stating that we will repeat certain steps until a pre-defined constraint has been reached.
• This makes designing algorithms quicker and simpler because they don’t have to include lots of unnecessary steps.
• It is easy to conceptualize or track how a problem can be solved iteratively.

<aside> 💡 Iteration is not the only way to deal with problems in which same problems are repeated.

</aside>

Consider the following example: compute the factorial of a given integer n

int factorial(int n){
    int fac = 1;
    int i;
    for(i = 1; i <= n; i++)
        fac = fac*i;
    return fac;
}

int fac(int n){
    if (n == 1)
        return 1;
    else
        return n*fac(n-1);
}