5.10. Recursion

Recursion consists on solving a problem by analyzing simpler cases of the same problem. A recursive function is one that "calls itself", reducing the complexity step by step until a trivial case is found. In mathematics we have several examples. One classic example is the "factorial of a number":

The "factorial" of 1 is 1:

  1! = 1

And the factorial of an arbitrary number is this number multiplied by the successive numbers, until 1 is reached:

  n! = n · (n-1) · (n-2) · ... · 3 · 2 · 1

(for instance, the factorial of 4 is 4 · 3 · 2 · 1 = 24)

If we think that the factorial of n-1 is

  (n-1)! = (n-1) · (n-2) · (n-3) · ... · 3 · 2 · 1

Then we can write the factorial of a number from the factorial of the following number:

  n! = n · (n-1)!

This is the recursive definition of the factorial, which could be programmed as:

/*---------------------------*/

/*  C# Example #57:          */

/*  example57.cs             */

/*                           */

/*  Recursive functions:     */

/*  factorial                */

/*                           */

/*  Intro to C#,             */

/*    Nacho Cabanes          */

/*---------------------------*/

using System;

public class Example57

{

  public static long fact(int n) {

   if (n==1)               // We make sure that it ends

     return 1;

   return n * fact (n-1);  // If it is not 1, recursion must go on

  }

  public static void Main()

  {

    int num;

    Console.WriteLine("Enter an integer number: ");

    num = Convert.ToInt32(System.Console.ReadLine());

    Console.WriteLine("Its factorial is: {0}", fact(num));

  }

 

}

Two important things to consider:

Ø  Pay attention to the first part of the recursive function: it is very important to check that there is a way to exit the function, so that our program is not left inside a loop all the time, leaving the computer (or the current task) "hung". We must find a "trivial case" to reach, and a way to decrease the complexity of the problem towards that trivial case.

Ø  Factorials grow rapidly, so we should not try large numbers: the factorial of 16 is 2,004,189,184, so after 17 we might get wrong results if we use "normal" integers.

How useful is this? More than it seems: many complicated problems can be expressed from a simpler one. In many such cases, the problem can be expressed recursively. Later we will see more examples.

Suggested exercises:

·       (5.10.1) Create a function that calculates the value of raising an integer to another integer (for example, 5 raised to 3 = 5³ = 5 × 5 × 5 = 125). This function must be created recursively.

·       (5.10.2) Alternatively, create a function that calculates the value of raising an integer to another integer non-recursively ("iteratively"), using the command "for".

·       (5.10.3) Create a program that uses recursion to calculate a Fibonacci number series (in which the first two items are 1, and for the other elements, each one is the sum of the preceding two).

·       (5.10.4) Create a program that uses recursion to calculate the sum of the elements of a vector.

·       (5.10.5) Create a program that uses recursion to calculate the greatest elements of a vector.

·       (5.10.6) Create a program that uses recursion to reverse a string of characters (for example, from "Hello" it would return "olleH").

·       (5.10.7) Create both recursively and iteratively, a function to say whether a string is symmetric (a palindrome). For example, "RADAR" is a palindrome.

·       (5.10.8) Create a program that finds the greatest common divisor of two numbers using Euclid's algorithm: Given two positive integers m and n, such that m>n, to find their greatest common divisor, ie, the largest positive integer that divides both: - Divide m by n to get the remainder r (0 ≤ r <n) - If r = 0, the GCD is n.; - Otherwise, the greatest common divisor is GCD (n, r).

·       (5.10.9) Create two functions to tell if a certain text is substring from a string. You cannot use "Contains" nor "IndexOf", but you must analyze the string one letter at a time. One function must be iterative and the other must be recursive.

·       (5.10.10) Create a function that receives a string and a substring, and returns how many times the substring can be found in the string, as subsequence formed from its letters in order. For example, if you get the word "Hhoola" and the substring "hola", the answer would be 4, because it could take the first H with the first O (and the L and A), the first H with the second O, the second H with the first O, or the second H with the second O. If you get "hobla", the answer would be 1. If you get "Ohla", the answer is 0, because there is no O after the H allowing to complete the sequence in order.