0

I have been warned by my professor to avoid "false recursion", where a function behaves recursively, but does no useful recursive work. I believe I understand recursion, but would like to double check.

I have written a short recursive sorting program that sorts (recursively I hope) the given array, ignoring the first element. After sorting all elements after the first, it places the first element in the correct place within the sorted sub-array (by shifting elements left).

The code is as follows:

#include <iostream> // for cout
using namespace std;

void RecSort(int*, int, int); //RecSort function declaration
int arr[8] = {4,1,2,7,5,9,0,2}; //global array to sort (just an example)

void RecSort(int* arr, int len, int curr)       { //RecSort definition
        if (curr < len - 2)     { //-1 to agrre with 0 indexing, -1 to stop 1 element before the end (terminating condition)
                RecSort(arr, len, curr + 1); //recursively sort all elements except first element
        }
        for (int i = curr; i < len - 2; i++)    { // once the rest of the array is sorted, shift elements to the left of the first element
                if (arr[i] > arr[i + 1])        { // while appropriate (in this case, sort ascending order)
                        int temp = arr[i + 1]; //swap array elements if needed
                        arr[i + 1] = arr[i];
                        arr[i] = temp;
                }
        }
}

int main()      {

int length, current;
RecSort(arr, length = 8, current = 0);// sort array (recursively?)
        for (int i = 0; i < length - 1; i++)    {
                cout << arr[i] << " "; //print array to verify functionality
        }
}

Does this appear to be truly recursive?

closed as off-topic by Scant Roger, jwenting, Mason Wheeler, user22815, user40980 Dec 14 '15 at 4:06

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions asking for assistance in writing or debugging existing code are off-topic on Programmers. These questions can be asked on Stack Overflow if they include the desired behavior, a specific problem or error, and the shortest code necessary to reproduce it in the question itself. See How To Create a Minimal, Complete, and Verifiable Example." – Scant Roger, jwenting, Community
If this question can be reworded to fit the rules in the help center, please edit the question.

5

I've never come across the term "false recursion" before, and it sounds like it might be terminology original to your professor. As a consequence, its a bit hard to judge what he thinks qualifies. I'll assume he means that the function can be easily rewritten using a loop instead of recursion, thus it didn't need to be recursive.

As a general rule of thumb, if a function needs to be recursive, it'll call itself multiple times. When a function only calls itself once, it can usually be rewritten as a loop.

In your case, what you are doing is sorting the last element, then the last two elements, then the last three elements, etc. You can implement this as loop something like:

for (int startIndex = length - 1, startIndex >= 0; startIndex++) {
    // do what you would have done before.

What you've done here is implemented an insertion sort, its not typically implemented in a recursive fashion.

  • Thanks for the input! I understand this doesn't need to be recursive. I believe "false recursion" is supposed to mean the function appears recursive (i.e. calls itself), but the recursive nature does nothing to advance the function towards an answer, and all the work (in this case sorting) is actually essentially done at the end of all the recursive calls and isn't a function of the recursion itself. Does this make sense? It is hard to explain without being wordy. I just want to make certain the recursive part of my function is helping to sort the array. – user207045 Dec 9 '15 at 19:08
  • What should be noted is that it's far from universal that recursion is a Dangerous Thing that should only be used on special occasions. Some languages always encourage using recursion over using loops (or may not even have loops). – GregRos Dec 9 '15 at 19:14
  • There isn't a function that needs to be recursive. There are function that are simplier in a recursive fashion but you could rewrite them using an external stack. – Scara95 Dec 9 '15 at 19:16
  • @user207045, sure, if all that your professor means is that the recursion does something, this qualifies. – Winston Ewert Dec 9 '15 at 19:20
  • 1
    All recursive functions can be reimplemented as iterative. To reimplement a real recursive function iteratively, you need to utilize a stack data structure. If a recursive function can be reimplemented to be iterative without the need of a stack, it is not a true recursive function. For example: add( a, b ) { if (b == 0) return a; return a + 1 + add( a, b - 1 ); } which can be trivially reimplemented as { return a + b; } – Mike Nakis Dec 9 '15 at 19:37

Not the answer you're looking for? Browse other questions tagged or ask your own question.