This page is no longer maintained — Please continue to the home page at www.scala-lang.org

Simply factorial problem; returning factorial call stack

1 reply
csg
Joined: 2012-02-11,
User offline. Last seen 42 years 45 weeks ago.
Hello all,

Practising my poor scala skills (and general programming) and in order to better understantig of recursion, I just want to build and return list of strings with the call stack.
For the well known factorial program:

factStringList(5) should return:

5*fact(4)
5*4*fact(3)
5*4*3*fact(2)
5*4*3*2*fact(1)
5*4*3*2*1

Here is my piece of code that does output:
5*4*3*2*fact(1)
4*3*2*fact(1)
3*2*fact(1)
2*fact(1)
fact(1)

def factString(n : Int): String = n match {
  case 1 => "f(1)"
  case _ =>  n.toString() + " * " + factString(n - 1)
}

def factStringList(n : Int): List[String] = n match {
  case 0 => Nil
  case _ => {
    val s = factString( n )
    s :: factStringList(n - 1)
  }
}

Any help?

Thanks.
ichoran
Joined: 2009-08-14,
User offline. Last seen 2 years 3 weeks ago.
Re: Simply factorial problem; returning factorial call stack
You need to think step-by-step through the code you've written.

For example, could your code possibly print f(n) for any n other than 1?

If you recurse from 5 down to three, could your code possibly know that it should have a 5*4* at the beginning of whatever comes next (that is, is there anything in your code that could generate that substring?).

You're going to need to pass some information forward into the recursion, in this style:

  def passItForward(n: Int, s: String = ""): String = {
    if (n <= 0) s else passItForward(n-1, s + "," + n.toString)
  }

  --Rex

On Mon, Feb 20, 2012 at 1:44 PM, csg <carlossg00 [at] gmail [dot] com> wrote:
Hello all,

Practising my poor scala skills (and general programming) and in order to better understantig of recursion, I just want to build and return list of strings with the call stack.
For the well known factorial program:

factStringList(5) should return:

5*fact(4)
5*4*fact(3)
5*4*3*fact(2)
5*4*3*2*fact(1)
5*4*3*2*1

Here is my piece of code that does output:
5*4*3*2*fact(1)
4*3*2*fact(1)
3*2*fact(1)
2*fact(1)
fact(1)

def factString(n : Int): String = n match {
  case 1 => "f(1)"
  case _ =>  n.toString() + " * " + factString(n - 1)
}

def factStringList(n : Int): List[String] = n match {
  case 0 => Nil
  case _ => {
    val s = factString( n )
    s :: factStringList(n - 1)
  }
}

Any help?

Thanks.

Copyright © 2012 École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland