INTRO TO RECURSION

A LECTURE FOR THE C++ COURSE

Each slide may have its own narration in an audio file. �For the explanation of any slide, click on the audio icon to start the narration.

​

The Professor‘s C++Course by Linda W. Friedman is licensed under a �Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.

RECURSION

What is recursion? A good way to explain recursion is to examine the factorial operation in math or on your calculator.

​

5! = 5*4*3*2*1 =120

​

factorial (5);

5 * factorial (4);

5* 4* factorial (3);

RECURSION

2

RECURSIVE FUNCTIONS

• Many problems can best be solved by breaking them down into smaller, similar problems.
• A recursive function is one that calls itself. How does that work?

RECURSION

3

LET’S START WITH AN EXAMPLE

• We would like to design a program that outputs the integers from 9 to 1.
• Or, from any integer down to 1.

​

RECURSION

4

WHAT WOULD YOU DO?

PRINTDOWNFROM()

//recursion.cpp

#include <iostream>

using namespace std;

void printdownfrom (int);

void print (int);

Int main(){

int n=9;

printdownfrom (n);

cout << "\n\n\n";

return 0;

}

​

void printdownfrom (int a){

if (a==1) print(1);

else {

print (a);

printdownfrom (a-1);

}

return;

}

void print (int n){

cout << n << endl;

return;

}

RECURSION

5

FACTORIAL

Some problems are inherently, recursive, e.g., the definition of a factorial: n! = n ∙ (n-1) ∙ (n-2) ∙ … ∙ (2) ∙ (1) = n ∙ (n-1)!

​

Can you code this with a loop? Try it.

​

Now try with recursion. How about:

​

​

PLAY COMPUTER….

WHAT HAPPENS?

RECURSION

6

double factorial (int x){

return x * factorial (x-1);

}

FACTORIAL

#include <iostream>

using namespace std;

double factorial (int); //recursive factorial function

const int MIN = 0;

const int MAX = 30;

int main(){

int n;

do{

cout << "Enter an integer between " <<MIN<< " and " << MAX << ": ";

cin >> n;

}while (n < MIN || n > MAX); //Q: Can we use an ‘if’ instead?

cout << n << "! = " << factorial(n) << endl;

return 0;

}

double factorial (int x){

if (x <=1) return 1;

else return x * factorial (x-1); //Q: is the else needed?

}

RECURSION

7

OUTPUT FROM FACTORIAL PROGRAM

RECURSION

8

HOW DOES THIS WORK? A TIMELINE

RECURSION

9

REVIEW

• Recursion
• Recursive functions

RECURSION

10

What did we learn in this lecture? Plenty. Some terms to jog your memory: