71.1. Writing a recursive function¶

Solving a “big” problem recursively means to solve one or more smaller versions of the problem, and using those solutions of the smaller problems to solve the “big” problem. In particular, solving problems recursively means that smaller versions of the problem are solved in a similar way. For example, consider the problem of summing values of an array. What’s the difference between summing the first 50 elements in an array versus summing the first 100 elements? You would use the same technique. You can even use the solution to the smaller problem to help you solve the larger problem.

Here are the basic four steps that you need to write any recursive function.

1 / 17 Settings

<<<>>>

Step 1: Write and define the prototype for the function.

• // Sums the first n elements of the array, arr
• int sum(int arr[], int n)

• int result = sum(arr, n);

• int result = sum(arr, 10);

• sum(arr, 2);
• sum(arr, 1);
• sum(arr, 0);

• // sums first n elements of arr
• sum(arr, n)

• // sum first n-1 elements of arr
• sum(arr, n - 1)

• // return sum of first n elements of arr
• return sum(arr, n - 1) + arr[n-1];

• if (base case) {
• // return some simple expression
• } else { // recursive case
• // some work before
• // recursive call
• // some work after
• }

Usual Format:

Alternative Format:

• if (recursive case) {
• // some work before
• // recursive call
• // some work after
• } else {
• // base case
• // return some simple expression
• }

Saving...
Server Error
Resubmit

Now le’t see some different ways that we could write Sum recursively.

1 / 6 Settings

<<<>>>

Here are a few variations on how to solve the sum problem recursively.

First Version

• int sum(int arr[], int n) {
• if (n == 0) {
• return 0;
• } else {
• int smallResult = sum(arr, n - 1);
• return smallResult + arr[n - 1];
• }
• }

Second Version

• int sum(int arr[], int n) {
• if (n == 0) {
• result = 0;
• } else {
• int smallResult = sum(arr, n - 1);
• result = smallResult + arr[n - 1];
• }
• return result;
• }

Third Version

• int sum(int arr[], int n) {
• if (n == 0) {
• return 0;
• } else {
• return sum(arr, n - 1) + arr[n - 1];
• }
• }

Fourth Version

• int sum(int arr[], int n) {
• if (n == 0) {
• return 0;
• }
• return sum(arr, n - 1) + arr[n - 1];
• }

Saving...
Server Error
Resubmit

long Fibonacci(int n) {
  if (n < 2) {
    return 1;   
  }
  return Fibonacci(n - 1) + Fibonacci(n - 2);
} 

long Fibonacci(int n) {
  if (n < 2) {
    return 1;   
  }
  return Fibonacci(n - 1) + Fibonacci(n - 2);
} 

long Fibonacci(int n) {
  if (n < 2) {
    return 1;   
  }
  return Fibonacci(n - 1) + Fibonacci(n - 2);
}