Recursion

​Recursive Solutions

• Recursion breaks problem into smaller identical problems

  • An alternative to iteration

• A recursive function calls itself

• Each recursive call solves an identical, but smaller, problem

• Test for base case enables recursive calls to stop

• Eventually, one of smaller problems must be the base case

1. How to define the problem in terms of a smaller problem of

   same type?

   base case

2. How does each recursive call diminish the size of the problem?

3. What instance of problem can serve as base case?

   recusive

4. As problem size diminishes, will you reach base case?

   reach to the base case, as the base case return a value, the recursive calls would return then get the final result

• Classic example--the factorial function:

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

Recursive definition

• As a C++ function:

// recursive factorial function
int fact(int n) {
    if (n == 0)
    return 1; // base case
    else
    return n * fact(n - 1); // recursive case
}

The Factorial of n

Recursive Functions - Purpose

• Recursive functions are used to reduce a complex problem to a simpler-to-solve problem.

• The simpler-to-solve problem is known as the base case

• Recursive calls stop when the base case is reached

Stopping the Recursion

• A recursive function must always include a test to determine if another recursive call should be made, or if the recursion should stop with this call

• In the factorial function, the test is:

  • if (n == 0)

• Recursion uses a process of breaking a problem down into smaller problems until the problem can be solved

• In the factorial function, a different value is passed to the function each time it is called

• Eventually, the parameter reaches the value in the test, and the recursion stops

Rules for Good Recursive Function

• One or more base cases

  • Always returns without further recursion

• One or more recursive function calls

  • Must get closer to base case

  • Don‘t forget to use the result of your recursive call!

Types of Recursion

• Direct

  • a function calls itself

• Indirect

  • function A calls function B, and function B calls function A

  • function A calls function B, which calls …, which calls function A

Solving Recursively Defined Problems

• The natural definition of some problems leads to a recursive solution

• Example: Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

• After the starting 0, 1, each number is the sum of the two preceding numbers

• Recursive solution:

  fib(n) = fib(n – 1) + fib(n – 2);

• Base cases:

  n <= 0, n == 1

int fib(int n) {
    if (n <= 0)
    return 0;
    else if (n == 1)
    return 1;
    else
    return fib(n – 1) + fib(n – 2);
}

Writing a String Backward

• Tracing: Write BAT backwards

• The initial call is made: s = “BAT”, length of s = 3 print T and write BA backwards

• The next call: s = “BA”, length of s = 2 print A and write B backwards

• The next call: s = “B”, length of s = 1 print B and write “” backwards

• The next call: s = “”, length of s = 0 do nothing, since the string has no characters

• Output: TAB

Recursion Memory Diagram

void rPrint(int n) {
    if (n<=0) {
        return;
    }
    cout << n << endl;
    rPrint(n-1);
}
int main() {
    int n = 1;
    do {
        cout << "Enter Number: ";
        cin >> n;
        cout << "Start Printing" << endl;
        rPrint(n);
        cout << "End Printing" << endl;
    } while (n>0);
}

Memory Diagram