sri ramanuja seva

(For part 1 of this tutorial on recursion, pls click here: Recursion – Part 1.)
In this lesson, we shall look at a few more simple problems on recursion, and their solutions.
Problems covered in this lesson:

• Find sum of numbers from 1 to n.
• Find n! (n factorial)
• Find 2^n (2 raised to the power n)
• Find a^n (a raised to the power n)

What is recursion?
Recursion is the technique of breaking down a problem into similar problems of smaller size, and then again breaking down those smaller problems into still more smaller problems, and so on. That is, we solve a problem by expressing it in terms of a smaller problem of the same type.

Two things to keep in mind in designing recursive solutions –

• What is the recursive formula? (How can we express the problem in terms of a smaller problem of the same type?)
• What is the base case? (When should the recursion end? What is that small problem for which we directly know the answer?)

Q.1. Compute the sum 1 + 2 + … + n, recursively.

Solution.
Let Sum(n) denote the sum n + (n-1) + … + 1.

• Recursive formula: Sum(n) is n + Sum(n-1).
• Base case: Sum(1) is 1.

// Program to compute 1 + 2 + ... + n, recursively. 
#include <stdio.h>
int Sum(int n) //recursive function to find n + (n-1) + ... + 1
{
    if (n == 1)  //base case
        return 1;
    return n + Sum(n - 1);   //recursive formula
}
int main()
{
    int m;
    printf("How many terms in the series? ");
    scanf("%d", &m); //get input from user. 
    printf("The desired sum is %d", Sum(m)); //call the function
    return 0;
}

Sample output: 
How many terms in the series? 4
The desired sum is 10

Q.2. Compute n! (n factorial) recursively.

Solution.

• Recursive formula: n! is n x (n-1)!
• Base case: 1! is 1.

//Program to compute n! recursively.
#include <stdio.h>
int factorial(int n) //compute n! recursively
{
    if (n == 1)  //base case
        return 1;  //1! is 1.
    return n * factorial(n - 1);   //recursive formula; n! is n x (n-1)!
}
int main()
{
    int m;
    printf("What factorial do you want to find? ");
    scanf("%d", &m);
    printf("%d! is %d", m, factorial(m)); //display the result. 
    return 0;
}

Sample output: 
What factorial do you want to find? 5
5! is 120

Q.3. Compute 2^n recursively.

Solution.

• Recursive formula: 2^n is 2 x 2^(n-1).
• Base case: 2^1 is 2.

//Program to find 2^n using recursion.
#include <stdio.h>
int powerOf2(int n) //compute 2^n recursively.
{
    if (n == 1)  //base case
        return 2;  //2^1 is 2.
    return 2 * powerOf2(n - 1);   //recursive formula; 2^n is 2 x 2^(n-1).
}
int main()
{
    int n;
    printf("What power of 2 do you want to find? ");
    scanf("%d", &n);
    printf("2^%d is %d", n, powerOf2(n));
    return 0;
}

sample output: 
What power of 2 do you want to find? 4
2^4 is 16

Q.4. Compute a^n recursively.

Solution.

• Recursive formula: a^n is a x a^(n-1).
• Base case: a^1 is a.

#include <stdio.h>
int power(int a, int n) //computes a^n recursively
{
    if (n == 1)
        return a;  //base case. a^1 is a.
    return a * power(a, n - 1); //recursive formula. a^n is a x a^(n-1).
}
int main()
{
    int a, n; //a is the base, and n is the exponent.
    printf("Enter the base: ");
    scanf("%d", &a);
    printf("Enter the exponent: ");
    scanf("%d", &n);
    printf("%d^%d is %d", a, n, power(a, n)); //call the function.
    return 0;
}

sample output: 
Enter the base: 3
Enter the exponent: 4
3^4 is 81

In this lesson, we saw a few problems on recursion. identified the recursive formula and base case for those problems, and translated that into C code.
(For the next part of this tutorial on recursion, pls see here: Recursion – Part 3.)
(For more on C Programming, you can click here: Posts on C Programming)