Help I need to convert numbers into English words using recursion

I have to convert positive integers from one to 999,999,999 into English words. It would be easy if I didn't need to use recursion, but my prof said if it is done any other way, it will be graded 0. I have trouble understanding the concept of recursion. Can anyone give an example on how to approach this problem?

update: I wrote a function but it gives a weird value

function test(n)
nameend = '';
names0 = 'zero';
names1 = {'', 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine', 'ten', 'eleven', 'twelve', 'thirteen', 'fourteen', 'fifteen', 'sixteen', 'seventeen', 'eighteen', 'nineteen'};
names20 = {'', 'twenty', 'thirty', 'forty', 'fifty', 'sixty', 'seventy', 'eighty', 'ninety'};
if n == -1
    disp(nameend);
end
if n == 0
    disp(names0);
end
if n >= 1000000
    n1 = floor(n/1000000);
  if n1 > 100
      num100 = floor(n1/100);
      word100 = names1{num100+1};
      if rem(n1,100) > 0
          disp(word100), disp('hundred'), disp('and');
      else
          disp(word100), disp('hundred'), disp('million');
      end
      n1 = rem(n1,100);
  end
  if n1 < 20 && n > 0
      word1 = names1{n1+1};
      disp(word1), disp('million');
  elseif n>0
      num10 = floor(n1/10);
      word10 = names20{num10};
      num1 = rem(n1,10);
      word1 = names1{num1+1};
      disp(word10); disp(word1); disp('million');
  else
      disp('million');
  end
  n = rem(n,1000000);
  test(n)
end
if 1000000 > n && n >=1000
  n1 = floor(n/1000);
  if n1 > 100
      num100 = floor(n1/100);
      word100 = names1{num100+1};
      if rem(n1,100) > 0
          disp(word100), disp('hundred'), disp('and');
      else
          disp(word100), disp('hundred'), disp('thousand');
      end
      n1 = rem(n1,100);
  end
  if n1 < 20 && n > 0
      word1 = names1{n1+1};
      disp(word1), disp('thousand');
  elseif n>0
      num10 = floor(n1/10);
      word10 = names20{num10};
      num1 = rem(n1,10);
      word1 = names1{num1+1};
      disp(word10); disp(word1); disp('thousand');
  else
      disp('thousand');
  end
  n = rem(n,1000);
  test(n)
end
if 1000 > n && n >= 1
  floor(n);
  if n > 100
      num100 = floor(n/100);
      word100 = names1{num100+1};
      if rem(n,100) > 0
          disp(word100), disp('hundred'), disp('and');
      else
          disp(word100), disp('hundred');
      end
      n = rem(n,100);
  end
  if n < 20
      word1 = names1{n+1};
        disp(word1);
    else
        num10 = floor(n/10);
        word10 = names20{num10};
        num1 = rem(n,10);
        word1 = names1{num1+1};
        disp(word10); disp(word1);
    end
end

For example, if I input 999,999,999 it outputs

nine hundred and ninety nine million nine hundred and ninety nine thousand nine hundred and ninety nine nine hundred and ninety nine nine hundred and ninety nine thousand nine hundred and ninety nine nine hundred and ninety nine

How do I stop it at the first nine hundred ninety nine?

Also if I enter 900800700 it outputs:

nine hundred million million eight hundred thousand thousand seven hundred seven hundred eight hundred thousand thousand seven hundred seven hundred

How do I stop it from displaying million, thousand twice?

[Rik]

Just think about how you would say the number yourself. 1-999 million 1-999 thousand 1-999 contains three times the same thing, as does 1-999 itself.

[Sun Woo Kim]

Does recursive mean that I just need to include the function inside the function? Then I have a good way to approach the problem

[Rik]

A function being recursive usually means that a function calls itself. A famous example is the factorial function:

function result=factorial_example(value)
if value==1
    result=1;
else
    result=value*factorial_example(value-1);
end
end

Answer 1

[Walter Roberson]

To solve this with recursion, you will need to know the following programming truth:

initialize the variables A, B, C, ...
for variable = initial : increment : final
  code section here that modifies the variables A, B, C, ...
  but does not modify initial or increment or final but can modify variable
end

can be replaced by

initialize the variables A, B, C, ...
[finalA, finalB, finalC, ...] = recursive_for(initial, increment, final, A, B, C, ...)

where

function [A, B, C, ...] = recursive_for(initial, increment, final, A, B, C, ...)
  if initial > final
    return   %final A, B, C, same as inputs
  end
  variable = initial;
  code section here that modifies the variables A, B, C, ...
  but does not modify initial or increment or final but can modify variable
  [A, B, C, ...] = recursive_for(initial + increment, final, A, B, C, ...)
end

There is theoretical study of the circumstances under which recursion of this form can be automatically detected and turned into internal "for" without making a function call -- something that is beneficial because function calls increase the stack depth, so programs that can detect that the modifications can internally be safely done "in-place" are a good thing. This particular form of recursion is known as "tail recursion": it has the property that when the first "return" is encountered that you can return all the way up, just propagating the new variable values unchanged until you hit the top level where you started the recursion.

There is another way to write recursion known as "head recursion" in which the test for continuing is the last thing that is done, that can be used to express the "do until" kind of programming structure, and that too turns out to be able to be handled specially by systems built to look for it.

MATLAB does not implement head recursion or tail recursion specially, so if your "for" loop would have over 500 entries, MATLAB will run out of stack space and kill the computation if you are working recursively.

[Sun Woo Kim]

Thanks for the effort but I cannot understand :(

[Walter Roberson]

I had to modify the logic to account for the way that the colon operator (':') compensates for round-off error.

Example:

Y = 0;
for X = 1 : .2 : 5
  Y = Y + X.^2;
end
Y

can be replaced by

Y = 0;
Y = recursive_for(1, .2, 5, Y);
Y

where

function [Y] = recursive_for(X, Y)
    if isempty(X); return; end
    Y = Y + X(1).^2;
    Y = recursive_for(X(2:end), Y);
end

Or even more compactly (works for relatively simple calculations)

function [Y] = recursive_for(X, Y)
    if isempty(X); return; end
    Y = recursive_for(X(2:end), Y + X(1).^2);
end

Now imagine,

function number_word = recursive_name(digits, number_word)
  if isempty(digits); return; end
  if length(digits) == 1
    handle 0 specially
    digit_names = {'one', 'two', 'three', ...};
    number_word = [number_word, ' ', digit_names{digits(1)}];
    return
 end
  if length(digits) == 2 && digits(1) == 1
    teen_names = {'ten', 'eleven', ...};
    number_word = [number_word, ' ', teen_names{digits(2)+1}];
    return
  end
  ....
  if length(digits) == 9
     number_word = recursive_name( digits(2:end), [recursive_name(digits(1), ''), ' hundred million'] );
     return
  end
end

Notice how handling the naming of the first digit in a group of three digits is done by recursively calling to name the first digit and following that by 'hundred million' and then recursively processing the rest of the digits.

This particular code structure is weak on handling the case where all of the initial digits are 0, which needs to be handled by the special name 'zero' whereas zero is not otherwise to occur (you need to code so that you don't say anything for 0 in any place other than the original input having been all 0).