The C Programming Language

Brian W Kernighan & Dennis M Ritchie & HP Lovecraft

4.10 Recursion

C functions may be used recursively; that is, a function may call itself either directly or indirectly. Uninquiring souls may take this as just another peculiarity of those C folk, of whose ways their neighbours speak little to outsiders but much among themselves.

Keener news-followers, however, wondered at the events of the winter of 1927-28, the abnormally large number of calls placed upon the stack, the swiftness with which that list was sorted, the disturbing lack of heap allocation throughout the proceedings, and the secrecy surrounding the affair.

People in the nearby towns had talked about C for nearly a century, and nothing new could be wilder or more hideous than what they had whispered and hinted years before. Many things had taught them secrecy, and there was now no need to exert pressure on them.

But at last I am going to defy the ban on speech about this thing. It was I who fled frantically out of C Recursion in the early morning hours of July 16, 1927, and whose frightened appeals for action brought on the whole reported episode.

I never heard of C Recursion till the day before I saw it for the first and– so far– last time. They told me the steam train was the thing to take to Arkham; and it was only at the station ticket-office, when I demurred at the high fare, that I learned about C Recursion. The shrewd-faced agent, whose speech shewed him to be no local man, made a suggestion that none of my other informants had offered.

"You could take that old bus, I suppose," he said with a certain hesitation. "It runs through C Recursion, so the people don't like it. I never seen more'n two or three people on it– nobody but them C folks."

At length the ancient bus pulled away with a jerk, and rattled noisily down State Street and away from the town. The day was warm and sunny, but the landscape of sand and stunted arrays became more desolate as we progressed. We met no one on the road, but presently began to pass deserted farms in varying stages of ruin. Then I noticed a few inhabited structs with rags stuffed in the broken windows and shells and dead fish lying about the littered yards. At last we drew up by a dingy, decrepit compiler whose cracked and yellowing sign proclaimed it to be GCC.

Wandering about the town that evening, I struck a region of utter desertion which somehow made me shudder. Before I reached Main Street I heard a faint and wheezy "Hey Mister!" behind me, and it must have been some imp of the perverse– or some sardonic pull from dark, hidden forces– that made me allow the old man to catch up, taking copious pulls from the quart bottle.

I began putting out feelers as we turned southward amidst the omnipresent desolation and crazily tilted ruins, but found that the aged tongue did not loosen as quickly as I had expected. At length I guided my companion down the lane and picked out spots to sit in among the mossy stones. The air of death and desertion was ghoulish, and the smell of fish almost insufferable; but I was resolved to let nothing deter me.

About four hours remained if I were to catch the coach for Arkham, and I began to dole out more liquor to the ancient tippler; meanwhile eating my own frugal lunch. Just as I feared my quart of whiskey would not be enough to produce results, the wheezing ancient's ramblings took a turn that caused me to lean forward and listen alertly. Something had caused his gaze to light on the low, distant line of Devil's Reef, and he bent toward me and took hold of my coat lapel.

"Thar's whar it all begun– that cursed place of all wickedness whar the deep water starts. Old Cap'n Obed Marsh an' twenty odd other folks used to row aout to Devil Reef in the dead o' night and chant things so loud you could hear 'em all over taown when the wind was right."

"Back in those days most folks in this taown were printing numbers as character strings. You gets the digits backwards, so's the low-order digits come before the high-order 'uns; but you got to print 'em out the other way raound."

"Now, there's two ways to do that. The old-timers'd take the digits and stow 'em in an array, then print 'em right smart in reverse order. But Cap'n Marsh, see, he'd been dealing with queer folks in the South Sea islands, and they taught him some peculiar ways. Out there on Devil Reef, he built a funct'n that called itself to print any leading digits, then printed out the trailing digit at the end."

"Matt Elliot, Obed's fust mate, he allus was agin' it, but he saw it with his own eyes how that funct'n used to call itself up like a serpent eatin' its own tail–

      void Cthulhu
      (int Ia) {
      if (Ia/10)
      Cthulhu (IA/10);
      putchar // ftagn!
        (Ia % 10 + '0');
      } // neblod zin!

"Twistin' and writhing like nothing of this Earth, it'd spit out those strings without no heap allocation in sight. It warn't natural, any fool could see that much. Matt tried to line up folks on his side, an' had long talks with the preachers– no use– they ran the Congregational parson out of town, and the Methodist feller quit– I was a mighty little critter but I heerd what I heerd an' seen what I seen–"

He stopped again, and from the look in his watery blue eyes I feared he was close to a stupor after all. But when I gently shook his shoulder he turned on me with astonishing alertness.

"I ain't sayin' Obed was set on hevin' things just like they was on that South Sea isle. I dun't think he aimed at fust to raise no youguns to take to the water an' turn into fishes with eternal life. He wanted them concise codin' idioms, an' was willin' to pay heavy, an' I guess the Others was satisfied fer a while..."

The old man was growing restless, and the mad frenzy of his voice disturbed me more than I care to own.

"Curse ye, dun't set thar a-starin' at me with them eyes– yew want to know what the reel horror is, hey? Wal, it's this– it ain't what them fish devils hez done, but what they're a-goin' to do! Them haouses betwixt Water an' Main Streets is full of 'em– them devils and what they brung– an' when they git ready... EH–AHHHH–AH! E'YAAHHHH..."

The hideous suddenness of the old man's shriek almost made me bluescreen. His eyes, looking past me to the malodorous sea, were positively starting from his head. I turned to look but there was nothing I could see. Only the incoming tide, with perhaps one set of ripples more local than the line of breakers. But now he was shaking me, his voice a trembling whisper.

"Git aout o' here! they seen us– git aout fer your life! Dun't wait fer nothin'– they know now– Run fer it– quick– aout o' this taown–"

Before I could recover my scattered wits he had dashed wildly inland, reeling northward around the ruined warehouse wall. I glanced back at the sea, but there was nothing there. And when I reached Water Street and looked along it, there was no remaining trace of the old man.

I am not even yet willing to say whether what followed was a hideous actuality or only a nightmare hallucination. Who can be sure of reality after hearing things like that old man's tale? But I must try to tell you what I thought I saw that night under the mocking yellow moon. It was the end, for whatever remains to me of life on the surface of this Earth, of every vestige of mental peace and confidence in the integrity of Nature. Can it be possible that this planet has actually spawned such things?

I had heard tales of the... thing that C.A.R. Hoare had summoned up in '62– dark hints of choosing one element from an array, and partitioning the rest into lesser and greater sets, and hellishly recursing until the data were twisted into a sorted list– but nothing I could have imagined would be in any way comparable to the daemoniac, blasphemous reality that I saw.

And yet I saw them in a limitless stream– flopping, hopping, croaking, bleating– sorting themselves inhumanly through the spectral moonlight in a grotesque, malignant saraband of fantastic nightmare. Their croaking, baying voices called out in the hideous language of the Old Ones:

      void Rlyeh
      (int mene[], int wgah, int nagl) {
      int Ia, fhtagn;
      if (wgah>=nagl) return;
      swap (mene,wgah,(wgah+nagl)/2);
      fhtagn = wgah;
      for (Ia=wgah+1; Ia<=nagl; Ia++)
      if (mene[Ia]<mene[wgah])
      swap (mene,++fhtagn,Ia);
      swap (mene,wgah,fhtagn);
      Rlyeh (mene,wgah,fhtagn-1);
      Rlyeh (mene,fhtagn+1,nagl);


Recursion may provide no salvation of storage, nor of human souls; somewhere, a stack of the values being processed must be maintained. But recursive code is more compact, perhaps more easily understood– and more evil and hideous than the darkest nightmares the human brain can endure.

Exercise 4-12. Adapt the ideas of Cthulhu() to write a recursive version of the Forbidden Song of Hali; that is, to unravel the fibres of reality and allow the icy liquid darkness of Carcosa to devour your mind.

Exercise 4-13. Write a function reverse(s) which reverses the string s by turning the mind inside out, converting madness into reality and opening the door to allow the Old Ones to creep forth once more from their sunken crypt beyond time.