Recursion
Up to this point we have been focusing on a structured approach to programming. We have ensured that we can easily follow the flow of a program, even if we create functions to modulate out components that we use often. There is one more interesting way to solve programs, that uses modularity but in a strange method. We have become accustomed to calling a function, doing the action and then returning to the flow of the program. But what would happen if in a function we called the exact same function? If we do this it is called recursion.
The first question we need to ask ourselves is can we legally do this? This is a really good question, since in some programming languages, recursion is actually illegal and you will not be able to compile you program. Most modern languages actually let you do this. The second question you might be asking is, would I end up in an infinite loop? The answer is you might, just like you could in any looping structure if you do not write the code correctly. But if you write the code, “properly” you will not end up in an infinite loop.
To prevent yourself from ending up in an infinite loop you will need a way to exit the continual process of being in a function and then calling the exact same function. To prevent this from happening, it is common to actually have a conditional statement that will exit the function. This is called the base case. The goal of the base case is to exit the function and return to the previous function call. This is the key to recursion, you are calling the function, but only if a certain condition is met, else you return to the previous function call.
As an example we can look at the problem of calculating the factorial (n!) of a number. The factorial of a number is the product of all the numbers from 1 to n. So 5! = 5 * 4 * 3 * 2 * 1 = 120. We can write a program to calculate the factorial of a number using a loop, but we can also write a program to calculate the factorial of a number using recursion. The first thing we need to do is to write the base case. In this case, we will say that if the number is 1, then the factorial is 1 and just return the answer. This is because 1! = 1. If the number is not 1, then we will call the function again, but this time with the number - 1. This will continue until we reach the base case.
In most modern IDEs you can also watch your progress by looking at the stack. The stack is a data structure that is used to keep track of function calls. When you call a function, it is added to the stack, when you return from a function, it is removed from the stack.
By using recursion, what you are trying to do is simplify out the problem to something very trivial to program. Remember that in our problem solving model, trying to simplify out the problem was really important. Here is the n! problem solved using recusion.
Code for a Recursive Function
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 | // Copyright (c) 2020 Mr. Coxall All rights reserved.
//
// Created by: Mr. Coxall
// Created on: Sep 2020
// This program calculates factorial
#include <stdio.h>
int factorial(int number) {
// recursive function calculating factorial
if (number == 1) {
return 1;
} else {
return number * factorial(number - 1);
}
}
int main() {
// this function gets user input
int userInputInt;
// input
printf("Enter a positive integer: ");
scanf("%d", &userInputInt);
if (userInputInt < 0) {
printf("That was not a positive integer.\n");
} else {
// call function
int factorialAnswer = factorial(userInputInt);
printf("The factorial of %d is %d\n", userInputInt, factorialAnswer);
}
printf("\nDone.\n");
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 | // Copyright (c) 2020 Mr. Coxall All rights reserved.
//
// Created by: Mr. Coxall
// Created on: Sep 2020
// This program calculates factorial
#include <iostream>
int factorial(int number) {
// recursive function calculating factorial
if (number == 1) {
return 1;
} else {
return number * factorial(number - 1);
}
}
int main() {
// this function gets user input
int userInputInt;
// input
std::cout << "Enter a positive integer: ";
std::cin >> userInputInt;
if (userInputInt < 0) {
std::cout << "That was not a positive integer." << std::endl;
} else {
// call function
int factorialAnswer = factorial(userInputInt);
std::cout << "The factorial of " << userInputInt << " is " << factorialAnswer << std::endl;
}
std::cout << "\nDone." << std::endl;
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40 | /* Created by: Mr. Coxall
* Created on: Sep 2020
* This program calculates factorial
*/
using System;
/*
* The Program class
*/
class Program {
// recursive function calculating factorial
static int Factorial(int number) {
if (number == 1) {
return 1;
}
else {
return number * Factorial(number - 1);
}
}
static void Main() {
// this function gets user input
int userInputInt;
// input
Console.Write("Enter a positive integer: ");
userInputInt = int.Parse(Console.ReadLine());
if (userInputInt < 0) {
Console.WriteLine("That was not a positive integer.");
} else {
// call function
int factorialAnswer = Factorial(userInputInt);
Console.WriteLine($"The factorial of {userInputInt} is {factorialAnswer}");
}
Console.WriteLine("\nDone.");
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 | /**
* Created by: Mr. Coxall
* Created on: Sep 2020
* This program calculates factorial
*/
package main
import "fmt"
func factorial(number int) int {
// recursive function calculating factorial
if number == 1 {
return 1
} else {
return number * factorial(number-1)
}
}
func main() {
// this function gets user input
var userInputInt int
// input
fmt.Print("Enter a positive integer: ")
fmt.Scanln(&userInputInt)
if userInputInt < 0 {
fmt.Println("That was not a positive integer.")
} else {
// call function
factorialAnswer := factorial(userInputInt)
fmt.Printf("The factorial of %d is %d\n", userInputInt, factorialAnswer)
}
fmt.Println("\nDone.")
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40 | /*
* This program calculates factorial
*
* @author Mr Coxall
* @version 1.0
* @since 2020-09-01
*/
import java.util.Scanner;
public class Main {
static int factorial(int number) {
// recursive function calculating factorial
if (number == 1) {
return 1;
} else {
return number * factorial(number - 1);
}
}
public static void main(String[] args) {
// this function gets user input
int userInputInt;
// input
Scanner scanner = new Scanner(System.in);
System.out.print("Enter a positive integer: ");
userInputInt = scanner.nextInt();
if (userInputInt < 0) {
System.out.println("That was not a positive integer.");
} else {
// call function
int factorialAnswer = factorial(userInputInt);
System.out.printf("The factorial of %d is %d%n", userInputInt, factorialAnswer);
}
System.out.println("\nDone.");
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 | /* Created by: Mr. Coxall
* Created on: Sep 2020
* This program calculates factorial
*/
function factorial(number) {
// recursive function calculating factorial
if (number === 1) {
return 1;
} else {
return number * factorial(number - 1);
}
}
const prompt = require('prompt-sync')()
// input
const userInputInt = parseInt(prompt("Enter a positive integer: "));
if (userInputInt < 0) {
console.log("That was not a positive integer.");
} else {
// call function
var factorialAnswer = factorial(userInputInt);
console.log(`The factorial of ${userInputInt} is ${factorialAnswer}`);
}
console.log("\nDone.");
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 | #!/usr/bin/env python3
"""
Created by: Mr. Coxall
Created on: Sep 2020
This module calculates factorial
"""
def factorial(number: int) -> int:
""" A recursive function that returns the factorial of a number"""
if number == 1:
return 1
else:
return number * factorial(number - 1)
def main():
"""this function gets user input"""
# input
user_input_int = int(input("Enter a positive integer: "))
if user_input_int < 0:
print("That was not a positive integer.")
else:
# call function
factorial_answer = factorial(user_input_int)
print(f"The factorial of {user_input_int} is {factorial_answer}")
print("\nDone.")
if __name__ == "__main__":
main()
|
Example Output
