"The Three Laws of Recursion" (in Optional Chapters)


#1

I am just curios if anyone has done the Self Check questions in “The Three Laws of Recursion”. The book suggests n <= 1 as the base case for a recursive function to calculate the factorial of a number. I’ve never been a fan of recursion, so perhaps I am nitpicking. But I disagree with the reasoning behind using it instead of n == 0:

  • Yes, it is “the most efficient:roll_eyes: (if you do insist on using recursion) because you do save yourself one recursive call. (Never mind that recursion in Python is wildly inefficient vs. iteration, to begin with).

  • But then no, it doesn’t keep “your program from crashing if you try to compute the factorial of a negative number”. You still need to explicitly check if n is negative (because the factorial of a negative number is undefined). Preferably, you’ll check for negative n before making a recursive call, thus negating the “efficiency advantage” of the proposed base case for negative n values.

I appreciate your thoughts.


#2

Hi Leonid.
I’m reading this chapter just now.
What I understand is that the base case is the condition that make your function stop calling itself.
If you watch the problem like a mathematician, you will see that if you want calculate factorial for 1, it returns 1, and if you want calculate factorial for 0, it returns 1 too. For any other number, the factorial is the multiplication of this number by the factorial of this number -1. And as mathematician, you want to be sure that every one of the possibilities are covered and well defined.

If you watch the problem as an programmer, that no matter so much the math behind the problem. You just need to code it correct and efficiently.
What I think is that inside of the black box (function) you do not need to consider two cases that return the same value separately.
If you can resume the tow cases in just 1 case, that is the most efficient way and then should to be your choice as programmer.
In this case
fact(0)=1 and fact(1)=1
Is the same to say
fact(0 or 1) =1
and then the base case is if n<=1

I not believe that the reason is to save the program for crash when the functions is called to calculate a negative number. As you said, it is not definite, and the validation should to be done before to call the function.
That mean, we are sure that the number is a positive integer before to call the function.