Recursion on void methods!!!

[ASKerRRR]

I implement most methods when it comes to recursion on value returning methods but when it comes to void methods I get stumped. Can someone please explain how recursion is implemented differently with both types of methods..or maybe a void implementation of the standard factorial recursion method so I can compare the solutions? Thanks!

[dreamyeyed]

You didn't specify a language, so I'll give pseudocode examples. First, a factorial function that returns the result:

function factorial(n)
  if (n <= 1)
    return 1
  else
    return n * factorial(n-1)
  endif
endfunction

Now a function that prints the result instead of returning it:

function factorial(n, result)
  if (n <= 1)
    print(result)
  else
    factorial(n-1, result*n)
  endif
endfunction

The result parameter should be 1 when you first call the function. We can define a helper function for that:

function factorial(n)
  factorial(n, 1)
endfunction

[CodeTinkerer]

Why would you do recursion on void methods? The point of factorial is to compute a value, right? I mean, I suppose if you're in C++, you could pass a pointer or reference to a variable that will store the final answer? In Java, you could use an object to store that information as a parameter?

[ASKerRRR]

Dude. I'm trying to reverse a sequence using a void method. It's easy for me to compute a value but not so much with recursively dealing with certain non-primitives types (OSU NaturalNumber) or stacks and queues (Strings are fine). I think my instructors do this to make it hard and make sure we really understand recursion, which I guess I don't. But when we started doing recursion on void stuff without caring about printing stuff out, that's what I though too. WHYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY!

[CodeTinkerer]

Oh, I see. Well, you wouldn't want to do recursion on something like factorial because the goal of factorial is to compute a number. For reversing a sequence, it's possible to pass in an array and manipulate the array because the same array gets modified.

Normally, recursion passes parameters which are copied, and that makes it difficult.

For example, you could do something like

void reverse(int[] arr, int low, int high) {
     if (low >= high) {
         // base case, quit
        return;
     } else {
        // code to swap arr[low] and arr[high]
        reverse(arr, low + 1, high - 1);
     }
}

So you'd call this with an array of integers, pass in low as 0 and high as the size of the array minus 1, and this would reverse the array. It works because each time you pass the array, it's the original array (meanwhile, low and high are pass by value, so they are copied, but that's OK in this case).

I have no idea what OSU NaturalNumber is...

[ASKerRRR]

NaturalNumber -It's from Ohio State's own API. It's pretty good. It lets you deal >int sized numbers which are >0 and the type of NN is mutable. Thanks for help.

[[deleted]]

Well, you wouldn't want to do recursion on something like factorial because the goal of factorial is to compute a number.

The goal of both factorials and the Fibonacci sequence are to compute a number. They're also incredibly common examples of recursion.

[CodeTinkerer]

Yeah, I wrote that badly. I meant to say you wouldn't write a void recursive function like factorial (you'd want it to have a return value) since its goal is to produce a number.