Recursion

Notes

Recursion is a programming concept whereby a function invokes itself.

Recursion is typically used to solve problems that are decomposable into subproblems that are just like the original problem, but a step closer to being solved.

Here’s a recursive function called foo.

What happens when this function is called?

foo will print a string and call itself, which will print another string and call itself again, which will print another string and call itself yet again... and on and on infinitely.

However, every time a function is called, some space is set aside in the stack called a frame and every function call results in a new frame being created. So, if foo calls itself infinitely, we’ll eventually run out of stack memory and try to access memory that doesn’t belong to us, in which case our program will fail with a segmentation fault.

To avoid this situation, we need to make sure there’s always a way to break out of recursive calls -- we’ll call this the base case. When the base condition is met, the function should return without making a recursive call. Let’s make sure we have a base case in the next example :)

For our next example, let’s think about the factorial operation. The factorial operation is a perfect candidate for recursion because it is a problem that can easily be broken up into similar smaller problems!

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

So if we want to calculate the factorial of 5, we can think of it as multiplying 5 by the factorial of 4:

5! = 5 * 4!

Similarly, to calculate the factorial of 4, we multiply 4 by the factorial of 3:

4! = 4 * 3!

And so on...

Let’s implement a factorial function in C!

This recursive function calculates the factorial of its integer argument, and unlike the last function we saw, this one has a base case!

Think through what happens when you pass this function an argument of 3:

  • factorial(3) returns 3 * factorial(2)
  • factorial(2) returns 2 * factorial(1)
  • factorial(1) is the base case and returns 1

Once the base case is reached, all of the factorial() calls will return in succession to give us an answer of 6.

Let’s see what’s going on in the stack as this recursive function executes!

Let’s zoom in on the stack as this function executes:

  • main() calls factorial(3)

Every function call results in a new frame being created. These frames are arranged on top of each other in the stack, with the frame for the most recently called function (the active frame) at the top.

  • main() calls factorial(3)
  • factorial(3) calls factorial(2)

factorial(2) is now the active frame.

  • main() calls factorial(3)
  • factorial(3) calls factorial(2)
  • factorial(2) calls factorial(1)

factorial(1) is now the active frame.

  • main() calls factorial(3)
  • factorial(3) calls factorial(2)
  • factorial(2) calls factorial(1)
  • factorial(1) returns 1 to factorial(2)

factorial(1) returns 1 to factorial(2). Its frame is destroyed, and the one for the function below (in this case factorial(2)) becomes active again.

  • main() calls factorial(3)
  • factorial(3) calls factorial(2)
  • factorial(2) calls factorial(1)
  • factorial(1) returns 1 to factorial(2)
  • factorial(2) multiplies 1 * 2 and returns 2 to factorial(3)

factorial(2) returns 2 to factorial(2). Its frame is destroyed, and the one for the function below (in this case factorial(3)) becomes active again.

  • main() calls factorial(3)
  • factorial(3) calls factorial(2)
  • factorial(2) calls factorial(1)
  • factorial(1) returns 1 to factorial(2)
  • factorial(2) multiplies 1 * 2 and returns 2 to factorial(3)
  • factorial(3) multiplies 2 * 3 and returns 6 to main()

factorial(3) returns 6 to main(). Its frame is destroyed, and the one for the function below (in this case main()) becomes active again.

Nice! Our function calculated the correct answer!

3! = 3 * 2 * 1 = 6

Slides ( / )

study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide

Sigma

Prerequisites:

Write a recursive function called sigma with a prototype of

int sigma (int n);

that adds the numbers 1 through n and returns the sum.

jharvard@run.cs50.net (~): ./a.out
Enter a positive integer: 5
15

Try out some pseudocode here!
#include <cs50.h>
#include <stdio.h>

int sigma(int n)
{
    // TODO
}

int main(int argc, char* argv[])
{
    // ask user for a positive integer
    int n;
    do
    {
        printf("Enter a positive integer: ");
        n = GetInt();
    }
    while (n < 1);
    
    // report answer
    printf("%i\n", sigma(n));
}

Binary Search

Prerequisites:

Write a recursive binary search function called search with a prototype of

bool search(int n, int array[], int lower, int upper);

that returns true if n is found in array and false otherwise.

jharvard@run.cs50.net (~): ./a.out
> 4
YES

Try out some pseudocode here!
#include <cs50.h>
#include <stdio.h>

#define SIZE 8

bool search(int n, int array[], int lower, int upper)
{   
    // TODO
}

int main(void)
{
    int numbers[SIZE] = { 4, 8, 15, 16, 23, 42, 50, 108 };
    printf("> ");
    int n = GetInt();
    if (search(n, numbers, 0, SIZE - 1))
    {
        printf("YES\n");
    }
    else 
    {
        printf("NO\n");
    }
}

Videos

study50 video thumbnail

Monday, Week 4

An introduction to recursion