[R] How to eliminate this for loop ?

[Bert Gunter]

1. The for loop is probably as or more efficient than recursion,
especially for large n (comments/corrections on this claim  from
cogniscenti are welcome);

2. One can **Always** express a for loop recursively -- that is the
nature of computer languages (comments/corrections again welcome).

3. Here is code that does it: Note that I have changed argument name
"c" to "const" to avoid confusion with the c() function

f <- function(n,b,const)
{
	if(length(const)< n-1)stop("const is too short")
	g <- function(i){
		if(i==1) 1
		else b*g(i-1)+ const[i-1]
		}
	g(n)
}

As David intimated, this produces a vector, not a list. Cast with
as.list if that's what you want.

Cheers,
Bert


On Mon, Nov 8, 2010 at 6:03 AM, David Winsemius <dwinsemius at comcast.net> wrote:
>
> On Nov 8, 2010, at 4:30 AM, Nick Sabbe wrote:
>
>> Whenever you use a recursion (that cannot be expressed otherwise), you
>> always need a (for) loop.
>
> Not necessarily true ... assuming "a" is of length "n":
>
> a[2:n] <- a[1:(n-1))]*b + cc[1:(n-1)]
> # might work if b and n were numeric vectors of length 1 and cc had length
>>= n. (Never use "c" as a vector name.)
> # it won't work if there are no values for the nth element at the beginning
> and you are building up a element by element.
>
> And you always need to use operations that appropriate to the object type.
> So if "a" really is a list, this will always fail since arithmetic does not
> work on list elements. If on the other hand, the OP were incorrect in
> calling this a list and "a" were a numeric vector, there might be a chance
> of success if the rules of indexing were adhered to. The devil is in the
> details and the OP has not supplied enough code to tell what might happen.
>
> --
> David.
>
>> Apply and the like do not allow to use the intermediary results (i.e.
>> a[i-1]
>> to calculate a[i]).
>>
>> So: no, it cannot be avoided in your case, I guess.
>>
>>
>> Nick Sabbe
>> --
>> ping: nick.sabbe at ugent.be
>> link: http://biomath.ugent.be
>> wink: A1.056, Coupure Links 653, 9000 Gent
>> ring: 09/264.59.36
>>
>> -- Do Not Disapprove
>>
>>
>>
>> -----Original Message-----
>> From: r-help-bounces at r-project.org [mailto:r-help-bounces at r-project.org]
>> On
>> Behalf Of PLucas
>> Sent: maandag 8 november 2010 10:26
>> To: r-help at r-project.org
>> Subject: [R] How to eliminate this for loop ?
>>
>>
>> Hi, I would like to create a list recursively and eliminate my for loop :
>>
>> a<-c()
>> a[1] <- 1; # initial value
>> for(i in 2:N) {
>>        a[i]<-a[i-1]*b - c[i-1] # b is a value, c is another vector
>> }
>>
>>
>> Is it possible ?
>>
>> Thanks
>> --
>> View this message in context:
>>
>> http://r.789695.n4.nabble.com/How-to-eliminate-this-for-loop-tp3031667p30316
>> 67.html
>> Sent from the R help mailing list archive at Nabble.com.
>>
>> ______________________________________________
>> R-help at r-project.org mailing list
>> https://stat.ethz.ch/mailman/listinfo/r-help
>> PLEASE do read the posting guide
>> http://www.R-project.org/posting-guide.html
>> and provide commented, minimal, self-contained, reproducible code.
>>
>> ______________________________________________
>> R-help at r-project.org mailing list
>> https://stat.ethz.ch/mailman/listinfo/r-help
>> PLEASE do read the posting guide
>> http://www.R-project.org/posting-guide.html
>> and provide commented, minimal, self-contained, reproducible code.
>
> David Winsemius, MD
> West Hartford, CT
>
> ______________________________________________
> R-help at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.
>



-- 
Bert Gunter
Genentech Nonclinical Biostatistics
467-7374
http://devo.gene.com/groups/devo/depts/ncb/home.shtml